// clang-format off
#include<bits/stdc++.h>
using namespace std;

#define il inline
#define mkp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define lll __int128
#define ll long long
#define db double
#define ldb long_double
#define sq(x) ((x)*(x))
#define For(i,j,k) for(int i=(j); i<=(k); ++i)
#define ForDown(i,j,k) for(int i=(j); i>=(k); --i)
#define pb push_back
#define FileIO(filename) freopen(filename ".in" ,"r",stdin);freopen(filename ".out" ,"w",stdout)
template<typename T> il void read(T &x){ x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x);read(y...); }
template<typename T> il T qpow(T x, ll y, T mod=numeric_limits<T>::max()){T ans=1;x%=mod;while(y){if(y&1)(ans*=x)%=mod;(x*=x)%=mod;y>>=1;}return ans;}

namespace _Debug {
template <typename T> inline void _debug(const char* format, T t) { cerr<<format<<'='<<t<<endl; }
template <class First, class... Rest> inline void _debug(const char* format, First first, Rest... rest) { while (*format != ',') cerr << *format++; cerr << '=' << first << ","; _debug(format + 1, rest...);}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& V) { os << "[ "; for (const auto& vv : V) os << vv << ", "; os << "]"; return os; }
#define debug(...) cerr<<"Line "<<__LINE__<<": ",_debug(#__VA_ARGS__, __VA_ARGS__);
};
using namespace _Debug;

// File head end
// clang-format on

const int MAXN = 2e5 + 5;
int n, q, a[MAXN], bit[MAXN], same = 0, samep = 0, tp = 0;
#define lowbit(x) (x & -x)
il void upd(int pos, int val) {
  while (pos <= n)
    bit[pos] += val, pos += lowbit(pos);
}
il int qry(int pos) {
  int __ans = 0;
  while (pos)
    __ans += bit[pos], pos -= lowbit(pos);
  return __ans;
}

il void init() {
  For(i, 1, n) same += a[i] == i, samep += (a[i] & 1) == (i & 1);
  ForDown(i, n, 1) {
    tp ^= (qry(a[i]) & 1);
    upd(a[i], 1);
  }
}

int main() {
  read(n, q);
  For(i, 1, n) read(a[i]);
  init();
  while (q--) {
    int u, v;
    read(u, v);
    tp ^= 1;
    same -= a[u] == u, samep -= (a[u] & 1) == (u & 1);
    same -= a[v] == v, samep -= (a[v] & 1) == (v & 1);
    swap(a[u], a[v]);
    same += a[u] == u, samep += (a[u] & 1) == (u & 1);
    same += a[v] == v, samep += (a[v] & 1) == (v & 1);
    if (tp)
      printf("%d\n", n);
    else if (samep != n)
      printf("%d\n", n - 1);
    else if (same != n)
      printf("%d\n", n - 2);
    [[unlikely]] else
      puts("-1");
  }

  return 0;
}

answer.code: In function ‘int main()’:
answer.code:75:18: error: expected primary-expression before ‘else’
   75 |     [[unlikely]] else
      |                  ^~~~