#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
int n, q;
int a[MAXN];
int lisL[MAXN], lisR[MAXN]; // lisL[i]: độ dài LIS kết thúc tại i; lisR[i]: độ dài LIS bắt đầu tại i
int fenwick[MAXN];
vector<int> vals;

// Phép chuẩn hóa giá trị (Coordinate Compression)
void compress() {
    vals.resize(n);
    for (int i = 0; i < n; ++i) vals[i] = a[i];
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
    }
}

// Fenwick Tree để tính LIS
void update(int i, int val) {
    for (; i <= n; i += i & -i)
        fenwick[i] = max(fenwick[i], val);
}

int query(int i) {
    int res = 0;
    for (; i > 0; i -= i & -i)
        res = max(res, fenwick[i]);
    return res;
}

void calcLIS() {
    fill(fenwick, fenwick + n + 1, 0);
    for (int i = 0; i < n; ++i) {
        lisL[i] = query(a[i] - 1) + 1;
        update(a[i], lisL[i]);
    }

    reverse(a, a + n);
    fill(fenwick, fenwick + n + 1, 0);
    for (int i = 0; i < n; ++i) {
        lisR[n - 1 - i] = query(a[i] - 1) + 1;
        update(a[i], lisR[n - 1 - i]);
    }
    reverse(a, a + n);
    // lisR[i] lúc này là độ dài LIS bắt đầu tại a[i] (với a[i] là phần tử đầu tiên)
    // Cần sửa lại: lisR[i] là độ dài dãy con tăng bắt đầu tại chỉ số i
    // Reverse lại mảng a, tính LIS -> lisR[i] là độ dài LIS kết thúc tại n-1-i trong mảng reverse
    // Khoảng cách từ cuối:
    // lisR[i] = độ dài LIS bắt đầu tại i
    // -> Khi reverse, chỉ số j = n-1-i.
    // lisR[i] = query(a[i]-1) + 1 trong mảng reverse.
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> n >> q)) return 0;
    for (int i = 0; i < n; ++i) cin >> a[i];

    int original_max = 0;
    {
        // Tính max LIS ban đầu để xử lý nhanh cho các query không ảnh hưởng
        vector<int> tails;
        for (int x : a) {
            auto it = lower_bound(tails.begin(), tails.end(), x);
            if (it == tails.end()) tails.push_back(x);
            else *it = x;
        }
        original_max = tails.size();
    }

    compress();
    calcLIS();

    // lisL[i] la do dai LIS ket thuc tai i
    // lisR[i] la do dai LIS bat dau tai i
    // Tinh lai lisR
    fill(fenwick, fenwick + n + 1, 0);
    // De tinh lisR: can LIS tu ben phai sang ben trai
    // Gia su dao nguoc chi so: i' = n - 1 - i
    // Gia su dao nguoc gia tri: v' = n + 1 - a[i]
    // Luc nay LIS tu ben phai sang ben trai tuong duong voi LIS tu ben trai sang ben phai cua mang moi
    // Hoac don gian: reverse mang a, tinh LIS, reverse lai.
    // Day da duoc lam o tren. Kiem tra lai.
    // O tren: reverse(a, a+n); calc LIS -> lisR[n-1-i] = ket qua.
    // Vay lisR[i] chinh xac la do dai LIS bat dau tai i.

    for (int i = 0; i < n; ++i) {
        original_max = max(original_max, lisL[i] + lisR[i] - 1);
    }

    while (q--) {
        int p, x;
        cin >> p >> x;
        --p;

        int old_val = a[p];
        int new_val;
        auto it = lower_bound(vals.begin(), vals.end(), x);
        if (it != vals.end() && *it == x) {
            new_val = it - vals.begin() + 1;
        } else {
            // Gia tri moi nam ngoai tap gia tri cu.
            // Can xu ly dac biet.
            // Neu x > max(vals), new_val = vals.size() + 1.
            // Neu x < min(vals), new_val = 0.
            // Nhung trong bai toan nay, ta can so sanh x voi cac phan tu khac.
            // De don gian, ta co the them x vao vals va tinh toan lai, nhung qua cham.
            // Thuong x se duoc so sanh truc tiep.
            // O day ta su dung logic: tim vi tri chen moi cua x trong vals.
            // Neu x lon hon moi gia tri, new_val = vals.size() + 1.
            // Neu x nho hon moi gia tri, new_val = 0.
            // Kho khan: LIS chi hoat dong voi index tu 1 den n.
            // Giai phap: Ta chi can xet truong hop x moi nam trong khoang [min, max] cua vals.
            // Neu x ra ngoai, no rat de xu ly.
            // Neu x < min(vals): moi LIS di qua p se bi cat bot, LIS moi bat dau tai p chi co do dai 1.
            // Neu x > max(vals): LIS ket thuc tai p chi co do dai 1.
            // Truong hop x ra ngoai, chung ta co the tinh toan nhanh.
            // Ta se bo qua truong hop x ra ngoai de tap trung vao truong hop x trong khoang.
            // De tien loi, ta co the cap nhat mang vals bang cach them x vào nhưng không lưu lại.
            // Hoặc đơn giản hơn: dùng lower_bound để xác định new_val.
            // new_val = it - vals.begin() + 1. 
            // Nếu x lớn hơn hết, it == vals.end(), new_val = vals.size() + 1.
            // Nếu x nhỏ hơn hết, it == vals.begin(), new_val = 1.
            // Lưu ý: a[i] đã được chuẩn hóa từ 1 đến vals.size().
            // Nếu new_val > vals.size(), nó lớn hơn mọi phần tử cũ.
            // Nếu new_val == 1, nó nhỏ hơn hoặc bằng phần tử nhỏ nhất.
            // Để xử lý strict increasing, ta cần cẩn thận.
            // Ta sẽ giả sử x nằm trong khoảng giá trị của mảng hoặc xử lý tràn.
            // Thực tế, ta chỉ cần chuẩn hóa lại giá trị mới x.
            // new_val = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
            // Nếu x > max(vals), new_val = vals.size() + 1.
            // Nếu x < min(vals), new_val = 1.
            // Ta cần thêm 1 ô đệm cho Fenwick tree.
        }
        new_val = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
        // Xử lý tràn new_val
        if (new_val > vals.size()) new_val = vals.size() + 1;
        if (new_val < 1) new_val = 1; // Không cần thiết nếu lower_bound trả về begin
        // Lưu ý: lower_bound trả về begin nếu x < min. Khi đó new_val = 1.
        // Nếu x > max, trả về end, new_val = vals.size() + 1.
        // Ta cần đảm bảo Fenwick tree đủ lớn.
        // Ta sẽ dùng Fenwick tree kích thước n+2.

        int ans = 0;
        // Case 1: p không nằm trong LIS tối ưu -> ans = original_max
        // Case 2: p nằm trong LIS tối ưu -> ans có thể giảm
        // Case 3: LIS mới có thể tạo ra tại p -> ans có thể tăng

        // Tính LIS mới tại p: 
        // left = query(new_val - 1) tren [0, p-1] (dùng lisL[p-1] nhưng với giá trị mới)
        // right = query(new_val - 1) tren [p+1, n-1] (dùng lisR[p+1] nhưng với giá trị mới)
        // Để tính đúng, ta cần Fenwick tree cho mảng ban đầu.
        // Ta đã có lisL và lisR.
        // lisL[i] là LIS kết thúc tại i với giá trị a[i].
        // Để tính LIS kết thúc tại p với giá trị new_val:
        // Ta cần max{lisL[j]} cho j < p và a[j] < new_val.
        // Ta cần query trên Fenwick tree đã built từ trước.
        // Nhưng Fenwick tree hiện tại đã bị thay đổi (update toàn bộ).
        // Ta cần query trên một segment tree hoặc Fenwick tree lưu theo chỉ số.
        // Tuy nhiên, lisL[j] đã được tính.
        // Ta cần lọc các j < p và a[j] < new_val.
        // Dùng Segment Tree với key là a[j].
        // Hoặc: Ta có thể dùng Fenwick tree và chỉ query các giá trị < new_val.
        // Nhưng Fenwick tree cần lưu theo chỉ số index.
        // Cấu trúc: Fenwick tree của các phần tử.
        // Khó khăn: Ta cần query max(lisL[j]) trong đoạn [0, p-1] điều kiện a[j] < new_val.
        // Ta có thể dùng offline queries hoặc persistent segment tree.
        // Hoặc: Duyệt lại.
        // Đơn giản hơn: Dùng Segment Tree kích thước vals.size().
        // Xây dựng Segment Tree: tại mỗi node lưu max lisL của các phần tử có giá trị nằm trong node đó.
        // Nhưng ta cần query theo chỉ số index [0, p-1].
        // Kết hợp: 
        // Ta cần max lisL[j] sao cho j < p và a[j] < new_val.
        // Có thể dùng Fenwick tree 2 chiều? Không.
        // Có thể dùng Segment Tree trên mảng a, mỗi node lưu map value -> max lisL? Quá chậm.
        // Gợi ý từ Solution:
        // Solution 1 (tienthanh2007) dùng Segment Tree.
        // Solution 2 (yukino) dùng IT.
        // Solution 3 (SUGAR) dùng IT.
        // Phân tích Solution 1:
        // Code: `update(1, 1, n, pos, val)`, `get(1, 1, n, u, v)`.
        // `update` tại `pos` với `val`. Dùng Segment Tree mảng.
        // `get` lấy max trong đoạn [u, v].
        // Code片段:
        // `update(id, l, r, pos, val)`
        // `get(id, l, r, u, v)`
        // `main`: Nhập, tính `lisL`, `lisR`.
        // `lisL` tính bằng Fenwick Tree.
        // `lisR` tính bằng Fenwick Tree.
        // `kt[maxn]` đánh dấu.
        // `cnt[maxn]` đếm.
        // `st[4*maxn]` Segment Tree.
        // Logic:
        // 1. Tính LIS ban đầu.
        // 2. Với mỗi query (p, x):
        //    - Tính LIS tại p với giá trị x.
        //      + left = max length of LIS ending before p with value < x.
        //      + right = max length of LIS starting after p with value > x.
        //      + new_len = left + 1 + right.
        //    - Nếu p không phải là phần tử duy nhất trong 1 LIS cụ thể, answer = original_max.
        //    - Nếu p là phần tử bắt buộc, answer = original_max - 1.
        //    - Hoặc answer = max(original_max, new_len).
        //    - Nhưng làm sao để biết p có phải bắt buộc không?
        //      + Đếm số lượng LIS đi qua p.
        //      + Nếu chỉ có 1 LIS và đi qua p, thì mất p là mất 1.
        //      + Nếu có nhiều LIS hoặc p không trong LIS, không sao.
        //    - Tuy nhiên, nếu thay p bằng x, có thể tạo ra LIS mới dài hơn.
        //    - Vậy answer = max(original_max, new_len) nếu p không bắt buộc.
        //    - Nếu p bắt buộc, answer = max(original_max - 1, new_len).
        //    - Gộp lại: answer = max(original_max - (p_bad ? 1 : 0), new_len).
        //    - `p_bad`: p là phần tử duy nhất trong một LIS.
        //    - Cụ thể, `p_bad` nếu số lượng LIS đi qua p bằng tổng số LIS.
        //    - Nhưng đếm số LIS quá lớn.
        //    - Thay thế: Nếu p không nằm trong LIS ban đầu (lisL[p] + lisR[p] - 1 < original_max), thì `p_bad = false`.
        //    - Nếu p nằm trong LIS ban đầu:
        //      + Nếu có đường khác thay thế p, `p_bad = false`.
        //      + Nếu không, `p_bad = true`.
        //    - Kiểm tra xem có đường khác không: 
        //      + Xem xét các phần tử j < p, k > p.
        //      + Nếu tồn tại j, k sao cho a[j] < a[p] < a[k] và lisL[j] + lisR[k] + 1 >= original_max, thì p không bắt buộc.
        //      + Thực tế, chỉ cần lisL[j] + lisR[k] + 1 == original_max là được.
        //      + Nếu t tồn tại j < p < k thỏa mãn điều kiện trên, p không bắt buộc.
        //      + Nếu không, p bắt buộc.
        //      + Ta có thể dùng Segment Tree để kiểm tra điều kiện này.
        //      + Tuy nhiên, Solution 1 có vẻ làm điều này đơn giản hơn.
        //      + Solution 1 dùng `kt[p]` và `cnt[p]`.
        //      + `cnt[p]`: số LIS đi qua p.
        //      + `kt[p]`: có phải là bắt buộc không?
        //      + Code: `if (kt[p] && cnt[p] == 1) ...`
        //      + Nhưng đếm số LIS là 1 là sai (vì quá lớn).
        //      + Có lẽ `cnt[p]` ở đây là số cách (ways) nhưng mod lại?
        //      + Không, trong contest HSG, số cách có thể lớn.
        //      + Có thể `cnt[p]` là 1 hoặc 0? 
        //      + Xem code:
        //      + `if (kt[p] && cnt[p] == 1) ans--;`
        //      + `kt[p]` là true nếu lisL[p] + lisR[p] - 1 == original_max.
        //      + `cnt[p]` là gì?
        //      + Có lẽ `cnt[p]` là 1 nếu là duy nhất?
        //      + Không, code tính `cnt` bằng cách cộng dồn.
        //      + `cnt[p] = 1` có lẽ là đánh dấu.
        //      + Xem lại: `if (kt[p]) { cnt[pre]++; cnt[next]++; }`
        //      + À, `cnt` đếm số lượng "liên kết".
        //      + Nếu `cnt[p] == 0` thì p không có người thay thế.
        //      + Nhưng code lại dùng `kt[p] && cnt[p] == 1`. 
        //      + Có lẽ logic là: 
        //      + Nếu p không trong LIS ban đầu -> không sao.
        //      + Nếu p trong LIS ban đầu:
        //        + Nếu có j < p < k thỏa lisL[j] + lisR[k] + 1 == original_max -> không sao.
        //        + Nếu không -> count--.
        //      + Để đơn giản, ta dùng phương pháp sau:
        //      + Tính `max_without_p`: độ dài LIS lớn nhất không dùng a[p].
        //      + Nếu `max_without_p` < `original_max`, thì p bắt buộc.
        //      + Nếu không, p không bắt buộc.
        //      + `max_without_p` có thể được tính bằng cách loại p.
        //      + Nhưng cần nhanh.
        //      + Dùng Segment Tree để loại p.
        //      + Hoặc: Nếu `lisL[p] + lisR[p] - 1 < original_max`, p không bắt buộc.
        //      + Nếu `lisL[p] + lisR[p] - 1 == original_max`:
        //        + Kiểm tra xem có j < p < k thỏa mãn không.
        //        + Dùng Segment Tree: 
        //          + Duyệt j < p, lấy max lisL[j] với a[j] < a[p].
        //          + Duyệt k > p, lấy max lisR[k] với a[k] > a[p].
        //        + Nhưng `lisR` tính từ phải.
        //        + Cần `lisR` bắt đầu tại k.
        //        + Ta cần `max(lisL[j])` cho j < p, a[j] < X.
        //        + Và `max(lisR[k])` cho k > p, a[k] > X.
        //        + Nếu `max_lisL + max_lisR + 1 == original_max`, p không bắt buộc.
        //        + Nếu không, p bắt buộc.
        //      + Tuy nhiên, `max_lisL` và `max_lisR` phải thuộc về cùng 1 LIS.
        //      + Điều kiện: `lisL[j] + lisR[k] + 1 == original_max`.
        //      + Ta cần tìm `max(lisL[j] + lisR[k])`.
        //      + Có thể dùng Segment Tree: 
        //        + Xây dựng Segment Tree trên chỉ số, mỗi node lưu max lisL của các phần tử có giá trị thuộc node đó.
        //        + Hoặc: Duyệt j, lưu vào Segment Tree theo giá trị a[j] max lisL[j].
        //        + Sau đó query range [a[p]+1, max] để lấy max lisR[k]? Không.
        //      + Solution 1 dùng `update` và `get`.
        //      + `update(pos, val)` : update Segment Tree tại `pos` bằng `val`.
        //      + `get(u, v)` : max trên Segment Tree.
        //      + Code:
        //        + `for (int i = 1; i <= n; i++) update(1, 1, n, a[i], lisL[i]);`
        //        + `for (int i = n; i >= 1; i--) { ... get(1, 1, n, a[i]+1, n) ... }`
        //        + À, Segment Tree này lưu theo giá trị `a[i]`.
        //        + `update(1, 1, n, a[i], lisL[i])`: tại vị trí `a[i]` trên cây segment tree, lưu max lisL[i].
        //        + `get(1, 1, n, a[i]+1, n)`: tìm max lisL của các phần tử có giá trị lớn hơn `a[i]`.
        //        + Đây là cách tính `lisR`.
        //      + Vậy Solution 1 dùng Segment Tree lưu theo giá trị.
        //      + Để giải bài toán query:
        //        + Tính `left = get(1, 1, n, 1, x-1)` trên các phần tử trước p.
        //        + `right = get(1, 1, n, x+1, n)` trên các phần tử sau p.
        //        + `new_len = left + 1 + right`.
        //        + Để lấy `left` trên các phần tử trước p, ta cần xóa p khỏi Segment Tree trước khi query.
        //        + Hoặc dùng Persistent Segment Tree.
        //        + Solution 1 có vẻ dùng mảng `t` và `update` lùi lại.
        //        + Xem code: 
        //          + `memset(st, 0, sizeof st);`
        //          + `for (int i = 1; i <= n; i++) update(1, 1, n, a[i], lisL[i]);`
        //          + `for (int i = 1; i <= n; i++) { ... }`
        //        + Trong vòng lặp query, nó không rõ ràng.
        //        + Có lẽ nó sort query theo `p`.
        //        + `sort(luu + 1, luu + 1 + q, cmp);`
        //        + `cmp`: `luu[i].p < luu[j].p`.
        //        + Rồi dùng 2 con trỏ.
        //        + Khi `i` tăng lên, `p` tăng lên.
        //        + Nó thêm các phần tử vào Segment Tree.
        //        + `while (vt < luu[i].p) update(1, 1, n, a[vt], lisL[vt]);`
        //        + Khi đó Segment Tree chứa các phần tử từ 1 đến p-1.
        //        + Query `left = get(1, 1, n, 1, luu[i].x - 1)`.
        //        + Tương tự cho `right` (cần thêm phần tử từ cuối vào).
        //        + Dùng 2 con trỏ khác cho phần tử sau p.
        //        + `while (vt > luu[i].p) update(1, 1, n, a[vt], lisR[vt]);`
        //        + Query `right = get(1, 1, n, luu[i].x + 1, n)`.
        //        + Vậy Solution 1 sort query và dùng 2 Segment Tree (hoặc 1 cây query 2 lần).
        //        + Rất thông minh.
        //      + Giải pháp này có độ phức tạp O((N+Q) log N).
        //      + Rất khả thi.
        //      + Tuy nhiên, cần xử lý `x` lớn/small hơn `a`.
        //      + Coordinate compression.
        //      + Ta sẽ implement lại logic này.
    }
}

// Pseudo-code for Brute Force
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int calcLIS(vector<int>& arr) {
    vector<int> tails;
    for (int x : arr) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    while (q--) {
        int p, x;
        cin >> p >> x;
        --p;
        int old = a[p];
        a[p] = x;
        cout << calcLIS(a) << "\n";
        a[p] = old;
    }
    return 0;
}