We indeed have concavity of here, but I don't know how to show it. If someone does, feel free to edit my answer.

EDIT2: Thanks to Jaehyun Koo over at Codeforces I now know how to show concavity. The following is a modified version of his proof.

Consider the array partitioning problem. In it we are given values $cost[A][B]$ representing the cost of interval $[a, b)$, and wish to partition the array into intervals $[0, x_{1}), [x_{1}, x_{2}), \dots, x_{k}, n)$. Let $DP[n][k]$ denote the maximum sum $\sum_{i = 0}^{k} cost[x_{i}][x_{i+1}]$, where $x_{0} = 0$, $x_{k+1} = n$. We claim that $DP[n][k]$ is concave if the costs are Monge, that is, for all $a \leq b \leq c \leq d$ we have $cost[a][d] + cost[b][c] \leq cost[a][c] + cost[b][d]$.

First we'll show that our problem is an instance of the array partitioning problem with Monge costs. Set $cost[a][b]$ to be the length of the longest increasing subsequence in the interval $[a, b)$. Then $DP[n][k]$ for this instance of the array partitioning problem equals $DP[n][k]$ for our longest increasing subsequence problem. It remains to show that the costs are Monge.

Choose $a \leq b \leq c \leq d$, and take any LIS $L_{a, d} = x_{1}, \dots, x_{cost[a][d]}$ in the interval $[a, d)$, and any LIS $L_{b, d} = y_{1}, \dots, y_{cost[b][c]}$ in the interval $[b, c)$. We will combine them into two increasing subsequences in the intervals $[a, c)$ and $[b, d)$ of equal total length. To do this, let $x_{i}$ be the first $x$ and $x_{j}$ be the last $x$ in $[b, c)$. If $x_{i} \leq y_{1}$, set $L_{a, c} = (x_{1}, \dots, x_{i-1}, y_{1}, \dots, y_{cost[b][c]})$, $L_{b, d} = (x_{i}, \dots, x_{cost[a][d]})$. If $x_{j} \geq y_{cost[b][c]}$ do the same reversed. Otherwise, exists some $t, h$ s.t. $y_{h} \leq x_{t} \leq y_{h+1}$. Then set $L_{a, c} = (x_{1}, \dots, x_{t}, y_{h+1}, \dots, y_{cost[b, c]})$ and $L_{b, d} = (y_{1}, \dots, y_{h}, x_{t+1}, \dots, x_{cost[a, d]})$. Hence our cost array is Monge.

Now we'll show that the array partitioning problem with Monge cost is concave. Note that $DP[n][k+2] - DP[n][k+1] \leq DP[n][k+1] - DP[n][k]$ is the same inequality as $DP[n][k+2] + DP[n][k] \leq 2 DP[n][k+1]$. Take any partitions $x_{0}, \dots, x_{k+3}$ and $y_{0}, \dots, y_{k+1}$ with values $DP[n][k+2]$ and $DP[n][k]$ respectively. Take any $0 \leq i \leq k$ such that $y_{i} \leq x_{i+1} \leq x_{i+2} \leq y_{i+1}$. Such $i$ always exists, as some interval $[y_{i}, y_{i+1}]$ must be the first such that the last $x$ before the end of the interval, $x_{j+2} \leq y_{i+1}$ has $j \geq i$, thus $x_{i+2} \leq x_{j+2} \leq y_{i+1}$ and $y_{i} \leq x_{i+1}$ as otherwise the interval $[y_{i-1}, y_{i}]$ would contain $x_{i+1}$ contradicting the minimality of $i$.

We make the partitions $y_{0}, \dots, y_{i}, x_{i+2}, \dots, x_{k+3}$ and $x_{0}, \dots, x_{i+1}, y_{i+1}, \dots, y_{k+1}$, both of length $k+1$. What is the difference in total value? Most terms cancel, but in the sum of values of the original we have $cost[x_{i+1}][x_{i+2}]$ and $cost[y_{i}][y_{i+1}]$, while in the new one we have $cost[y_{i}][x_{i+2}]$ and $cost[x_{i+1}][y_{i+1}]$. But since $y_{i} \leq x_{i+1} \leq x_{i+2} \leq y_{i+1}$, by the Monge property $cost[y_{i}][y_{i+1}] + cost[x_{i+1}][x_{i+2}] \leq cost[y_{i}][x_{i+2}] + cost[x_{i+1}][y_{i+1}]$, hence the total value can only increase, and $DP[n][k+2] + DP[n][k] \leq 2 DP[n][k+1]$.

Note that we can modify the $\mathcal{O}(n \log n)$ algorithm to calculate the minimum and maximum values of $b$ that achieve the maximum value with the specific $\lambda$ with no increase in complexity. We can always find a $\lambda$ for which $\min_{b} \leq k \leq \max_{b}$, but this doesn't guarantee that there exists some subsequence with $k$ exceptions achieving the maximum. However, if we can show that $DP[n][b]$ is concave, i.e. $DP[n][b+2] - DP[n][b+1] \leq DP[n][b+1] - DP[n][b]$, we get this result, as we know that $DP[n][\min_{b} + 1] \leq DP[n][\min_{b}] + \lambda$ (due to maximality), therefore $DP[n][\max_{b}] \leq DP[n][k] + (\max_{b} - k) \lambda$, hence $DP'[n] = DP[n][\max_{b}] - \lambda \max_{b} \leq DP[n][k] - \lambda b$ and there exists a subsequence with $k$ exceptions achieving the maximum.

Note that we can modify the $\mathcal{O}(n \log n)$ algorithm to calculate the minimum and maximum values of $b$ that achieve the maximum value with the specific $\lambda$ with no increase in complexity. We can always find a $\lambda$ for which $\min_{b} \leq k \leq \max_{b}$, but this doesn't guarantee that there exists some subsequence with $k$ exceptions achieving the maximum. However, if we can show that $DP[n][b]$ is concave, i.e. $DP[n][b+2] - DP[n][b+1] \leq DP[n][b+1] - DP[n][b]$, we get this result, as we know that $DP[n][\min_{b} + 1] \leq DP[n][\min_{b}] + \lambda$ (due to maximality), therefore $DP[n][\max_{b}] \leq DP[n][k] + (\max_{b} - k) \lambda$, hence $DP'[n] = DP[n][\max_{b}] - \lambda \max_{b} \leq DP[n][k] - \lambda k$ and there exists a subsequence with $k$ exceptions achieving the maximum.

EDIT: Here is a C++ program for finding a maximal subsequence in $\mathcal{O}(n \log^{2} n)$. I use a segment tree for the range maximum data structure.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int INF = 2 * (int)1e9;

pair<ll, pair<int, int>> combine(pair<ll, pair<int, int>> le, pair<ll, pair<int, int>> ri) {
    if (le.first < ri.first) swap(le, ri);
    if (ri.first == le.first) {
        le.second.first = min(le.second.first, ri.second.first);
        le.second.second = max(le.second.second, ri.second.second);
    }
    return le;
}

// Specialised range maximum segment tree
class SegTree {
    private:
        vector<pair<ll, pair<int, int>>> seg;
        int h = 1;

        pair<ll, pair<int, int>> recGet(int a, int b, int i, int le, int ri) const {
            if (ri <= a || b <= le) return {-INF, {INF, -INF}};
            else if (a <= le && ri <= b) return seg[i];
            else return combine(recGet(a, b, 2*i, le, (le+ri)/2), recGet(a, b, 2*i+1, (le+ri)/2, ri));
        }
    public:
        SegTree(int n) {
            while(h < n) h *= 2;
            seg.resize(2*h, {-INF, {INF, -INF}});
        }
        void set(int i, pair<ll, pair<int, int>> off) {
            seg[i+h] = combine(seg[i+h], off);
            for (i += h; i > 1; i /= 2) seg[i/2] = combine(seg[i], seg[i^1]);
        }
        pair<ll, pair<int, int>> get(int a, int b) const {
            return recGet(a, b+1, 1, 0, h);
        }
};

// Binary searches index of v from sorted vector
int bins(const vector<int>& vec, int v) {
    int low = 0;
    int high = (int)vec.size() - 1;
    while(low != high) {
        int mid = (low + high) / 2;
        if (vec[mid] < v) low = mid + 1;
        else high = mid;
    }
    return low;
}

// Finds longest strictly increasing subsequence with at most k exceptions in O(n log^2 n)
vector<int> lisExc(int k, vector<int> vec) {
    // Compress values
    vector<int> ord = vec;
    sort(ord.begin(), ord.end());
    ord.erase(unique(ord.begin(), ord.end()), ord.end());
    for (auto& v : vec) v = bins(ord, v) + 1;

    // Binary search lambda
    int n = vec.size();
    int m = ord.size() + 1;
    int lambda_0 = 0;
    int lambda_1 = n;
    while(true) {
        int lambda = (lambda_0 + lambda_1) / 2;
        SegTree seg(m);
        if (lambda > 0) seg.set(0, {0, {0, 0}});
        else seg.set(0, {0, {0, INF}});

        // Calculate DP
        vector<pair<ll, pair<int, int>>> dp(n);
        for (int i = 0; i < n; ++i) {
            auto off0 = seg.get(0, vec[i]-1); // previous < this
            off0.first += 1;

            auto off1 = seg.get(vec[i], m-1); // previous >= this
            off1.first += 1 - lambda;
            off1.second.first += 1;
            off1.second.second += 1;

            dp[i] = combine(off0, off1);
            seg.set(vec[i], dp[i]);
        }

        // Is min_b <= k <= max_b?
        auto off = seg.get(0, m-1);
        if (off.second.second < k) {
            lambda_1 = lambda - 1;
        } else if (off.second.first > k) {
            lambda_0 = lambda + 1;
        } else {
            // Construct solution
            ll r = off.first + 1;
            int v = m;
            int b = k;
            vector<int> res;
            for (int i = n-1; i >= 0; --i) {
                if (vec[i] < v) {
                    if (r == dp[i].first + 1 && dp[i].second.first <= b && b <= dp[i].second.second) {
                        res.push_back(i);
                        r -= 1;
                        v = vec[i];
                    }
                } else {
                    if (r == dp[i].first + 1 - lambda && dp[i].second.first <= b-1 && b-1 <= dp[i].second.second) {
                        res.push_back(i);
                        r -= 1 - lambda;
                        v = vec[i];
                        --b;
                    }
                }
            }
            reverse(res.begin(), res.end());
            return res;
        }
    }
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> vec(n);
    for (int i = 0; i < n; ++i) cin >> vec[i];

    vector<int> ans = lisExc(k, vec);
    for (auto i : ans) cout << i+1 << ' ';
    cout << '\n';
}