#include <bits/stdc++.h>
using namespace std;
vector<int> fwc(200010, 0);
void add(int x)
{
    for (int i = x + 1; i < fwc.size(); i += i & -i)
        fwc[i]++;
}
int cnt(int x)
{
    int res = 0;
    for (int i = x + 1; i > 0; i -= i & -i)
        res += fwc[i];
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    int count_odd = 0;
    int count_right = 0;
    int count_sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        v[i]--;
        count_odd += ((i - v[i]) % 2 != 0);
        count_right += v[i] == i;
        // cout << ((i - v[i]) % 2 != 0) << " ";
    }
    // cout << endl;
    // cout << count_odd << endl;
    for (int i = 0; i < n; i++)
    {
        count_sum += i - cnt(v[i]);
        add(v[i]);
    }
    count_sum &= 1;
    for (int i = 0, a, b; i < q; i++)
    {
        cin >> a >> b;
        // cout << a << " " << b << "    ";
        a--;
        b--;
        count_odd -= ((a - v[a]) % 2 != 0);
        count_odd -= ((b - v[b]) % 2 != 0);
        count_right -= (a == v[a]);
        count_right -= (b == v[b]);
        // cout << ((a - v[a]) % 2 != 0) << " " << ((b - v[b]) % 2 != 0) << "    ";
        swap(v[a], v[b]);
        // cout << ((a - v[a]) % 2 != 0) << " " << ((b - v[b]) % 2 != 0) << "    ";
        count_odd += ((a - v[a]) % 2 != 0);
        count_odd += ((b - v[b]) % 2 != 0);
        count_right += (a == v[a]);
        count_right += (b == v[b]);
        count_sum ^= 1;
// if (count_right == n)
//     cout << -1 << endl;
// else if (count_odd == 0)
//     cout << n - 2 << endl;
// else if (count_sum)
//     cout << n << endl;
// else
//     cout << n - 1 << endl;
#define endl '\n'
        if (count_sum)
            cout << n << endl;
        else if (count_odd)
            cout << n - 1 << endl;
        else if (count_right == n)
            cout << -1 << endl;
        else
            cout << n - 2 << endl;
    }
}
// 41325 14325