#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
const int sz = 2e5 + 5, mod = 1e9 + 7;
int n, bit[sz];
//bit is 1 based indexing
//at x index update delta
void update(int x) {
    for(; x <= n; x += x&-x) {
        bit[x]++;
    }
}
//query sum from 1 to x index
int query(int x) {
    int sum = 0;
    for(; x > 0; x -= x&-x) {
        sum += bit[x];
    }
    return sum;
}
int query(int l, int r) {
   return query(r) - query(l - 1);
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int q; cin >> n >> q;
    std::vector<int> v(n + 1);
    std::vector<int> v1(n + 1);
    int odd = 0, thik = 0;
    for(int i = 1; i <= n; i++) {
        cin >> v[i];
        update(v[i]);
        v1[i] += query(v[i] + 1, n);
    }
    for(int i = 1; i <= n; i++) bit[i] = 0;
    ll tot = 0;
    for(int i = n; i >= 1; i--) {
        update(v[i]);
        v1[i] += query(1, v[i] - 1);
        tot += v1[i];
        v1[i] %= 2;
        odd += v1[i];
        thik += v[i] == i;
    }
    tot /= 2;
    tot %= 2;
    while(q--) {
        int a, b; cin >> a >> b;
        if(a != b) {
            int len = abs(b - a);
            thik -= ((v[a] == a) + (v[b] == b));
            thik += (v[a] == b) + (v[b] == a);
            if(len&1) {
                odd -= ((v1[a]&1) + (v1[b]&1));
                v1[a] ^= 1;
                v1[b] ^= 1;
                odd += (v1[a]&1) + (v1[b]&1);
                swap(v1[a], v1[b]);
            }
            tot ^= 1;
            swap(v[a], v[b]); 
        }
        int ans;
        if(thik == n) ans = -1;
        else if(tot) ans = n;
        else if(odd) ans = n - 1;
        else ans = n - 2;
        cout << ans << "\n"; 
    }
    return 0; 
}