#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;

struct Fenwick {
    Fenwick(int n) {
        this->n = n;
        data.resize(n + 1);
    }

    void add(int pos, int val) {
        for (int i = pos; i <= n; i += lsb(i)) {
            data[i] += val;
        }
    }

    int get(int pos) {
        int answer = 0;
        for (int i = pos; i > 0; i -= lsb(i)) {
            answer += data[i];
        }
        return answer;
    }

    vector<int> data;
    int n;
};

int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, q;
    cin >> n >> q;

    vector<int> arr(n + 1);
    int placed = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        placed += (arr[i] == i);
    }

    Fenwick pref(n + 1), suff(n + 1);
    vector<int> inv(n + 1);
    for (int i = 1; i <= n; i++) {
        pref.add(arr[i], 1);
        inv[i] = i - pref.get(arr[i]);
    }

    ll answer = 0;
    for (int i = n; i >= 1; i--) {
        inv[i] += suff.get(arr[i]);
        suff.add(arr[i], 1);
        answer += inv[i];
        inv[i] %= 2;
    }

    answer /= 2;
    answer %= 2;

    int odd = 0;
    for (int i = 1; i <= n; i++) {
        odd += (inv[i] % 2 == 1);
    }

    for (int tt = 1; tt <= q; tt++) {
        int l, r;
        cin >> l >> r;

        answer ^= 1;
        placed -= (arr[l] == l);
        placed -= (arr[r] == r);
        swap(arr[l], arr[r]);
        placed += (arr[l] == l);
        placed += (arr[r] == r);

        if (placed == n) {
            cout << -1 << "\n";
        } else {
            odd -= (inv[l] % 2);
            odd -= (inv[r] % 2);

            inv[l] += r - l - 2;
            inv[r] += r - l - 2;
            inv[l] %= 2;
            inv[r] %= 2;

            odd += (inv[l] % 2);
            odd += (inv[r] % 2);

            if (answer == 1) {
                cout << n << "\n";
            } else if (odd > 0) {
                cout << n - 1 << "\n";
            } else {
                cout << n - 2 << "\n";
            }
        }
    }

    return 0;
}