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

#define ff    first
#define ss    second
#define pb    push_back

typedef long long    ll;
typedef pair<ll,ll>    ii;
typedef long double    lf;


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll SQ = 320;
const ll N = 2e5+5;
const ll mod = 998244353;
const ll oo = 1e18;

int bit[N];

void update (int i, int x) {
  for (++i; i < N; i += (i & (-i))) bit[i] += x;
}

int query (int i) {
  int sum = 0;
  for (++i; i; i -= (i & (-i))) sum += bit[i];
  return sum;
}

int main(){
  #ifdef LOCAL
  freopen("input.txt","r",stdin);
  #endif // LOCAL
  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);

  int n, q; cin >> n >> q;
  vector <int> p(n);
  for (auto &e : p) cin >> e;

  int cnt = 0;
  vector <int> parity(n);
  vector <int> val(n);
  for (int i = 0; i < n; ++i) cnt += (p[i] == i + 1);
  int invs = 0;
  for (int i = n - 1; i >= 0; --i) {
    int x = query(p[i]);
    val[i] += x;
    invs += x;
    update (p[i], 1);
  }
  for (int i = 0; i < N; ++i) bit[i] = 0;
  int nodd = 0;
  for (int i = 0; i < n; ++i) {
    int x = query(n - p[i]);
    val[i] += x;
    parity[i] = val[i]%2;
    nodd+=parity[i];
//    cout << i << ' ' << val[i] << '\n';
    update(n - p[i], 1);
  }


//  cout << invs << '\n';
  for (int i = 0; i < q; ++i) {
    int u, v; cin >> u >> v;
    u--;v--;

    cnt -= (p[u] == u + 1);
    cnt -= (p[v] == v + 1);
    nodd -= (parity[u] + parity[v]);
    swap(p[u], p[v]);
    cnt += (p[u] == u + 1);
    cnt += (p[v] == v + 1);

    if (abs(v - u) % 2) {
      int sv = parity[v];
      parity[v] = parity[u] ^ 1;
      parity[u] = sv ^ 1;
      nodd += (parity[u] + parity[v]);
    }


    if (cnt == n) cout << -1 << '\n';
    else {
      if (invs % 2 == i % 2) cout << n << '\n';
      else {
        if (nodd) cout << n - 1 << '\n';
        else cout << n - 2 << '\n';
      }
    }
  }
  return 0;
}