#include <iostream>
#include <algorithm>
#include <vector>

typedef long long ll;
typedef long double lb;

#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file_in freopen("input.txt", "r", stdin);
#define file_in_out freopen("knapsack.in", "r", stdin); freopen("knapsack.out", "w", stdout);
#define all(x) (x).begin(), (x).end()

using namespace std;

int nvp(vector<int> &v) {
    int n = v.size();
    vector<int> dp(n, 1);
    vector<int> t(n + 1, 1);
    t[0] = 0;
    for (int i = 1; i < n; ++i) {
        dp[i] = max(dp[i], t[v[i] - 1] + 1);
        t[v[i]] = dp[i];
    }
    return *max_element(all(dp));
}

int main() {
    fast
//  file_in
//  file_in_out

    int n, q, a, b;
    cin >> n >> q;
    vector<int> v(n);
    cin >> v;
    cout << n - nvp(v) << endl;
    while (q--) {
        cin >> a >> b;
        swap(v[a - 1], v[b - 1]);
        cout << n - nvp(v) << endl;
    }
    return 0;
}