#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl
const int N = 1e5 + 10;
const int M = 2e4;
int read() {
int x = 0, f = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
return x * f;
}
int n, m, cnt, B;
int a[N], pos[N], bit[N], id[N], L[M], R[M];
int v[N], b[M][M], d[M][M], c[M];
void upd(int x) {
for (; x <= n; x += x & -x) bit[x] ^= 1;
}
int qry(int x) {
int res = 0;
for (; x; x -= x & -x) res ^= bit[x];
return res;
}
void psdw(int o) {
int len = R[o] - L[o] + 1;
for (int i = 1; i <= len; i++)
v[pos[b[o][i]]] = (v[pos[b[o][i-1]]] ^ d[o][i]);
}
void psup(int o) {
int len = R[o] - L[o] + 1;
c[o] = 0;
for (int i = 1; i <= len; i++)
c[o] += (d[o][i] = (v[pos[b[o][i]]] ^ v[pos[b[o][i-1]]]));
}
void build() {
for (int i = 1; i <= n; i++) {
id[i] = (i - 1) / B + 1;
if (i == 1 || id[i] != id[i-1]) L[id[i]] = i, cnt++;
R[id[i]] = max(R[id[i]], i);
}
for (int o = 1; o <= cnt; o++) {
int len = R[o] - L[o] + 1;
for (int i = 1; i <= len; i++) b[o][i] = a[L[o]+i-1];
sort(b[o] + 1, b[o] + 1 + len), psup(o);
}
}
int cg(int o, int x) {
int len = R[o] - L[o] + 1;
int p = lower_bound(b[o] + 1, b[o] + 1 + len, x) - b[o];
int res = ((p - 1) & 1);
if (p <= len) c[o] -= d[o][p], c[o] += (d[o][p] ^= 1);
return res;
}
void mdf(int o, int x, int y) {
int len = R[o] - L[o] + 1, p;
for (p = 1; p <= len; p++) if (b[o][p] == x) break;
for (int i = p; i < len; i++) b[o][i] = b[o][i+1];
for (p = 1; p < len; p++) if (b[o][p] > y) break;
for (int i = len; i > p; i--) b[o][i] = b[o][i-1];
b[o][p] = y;
}
void work(int x, int y) {
if (id[x] == id[y]) {
psdw(id[x]);
for (int i = x + 1; i < y; i++) v[i] ^= ((a[i] > a[y]) ^ (a[i] > a[x]));
for (int i = x; i < y; i++) if (a[y] > a[i]) v[y] ^= 1;
for (int i = y; i > x; i--) if (a[x] > a[i]) v[x] ^= 1;
swap(a[x], a[y]), swap(pos[a[x]], pos[a[y]]), swap(v[x], v[y]);
return psup(id[x]);
}
psdw(id[x]), psdw(id[y]);
for (int i = x + 1; id[i] == id[x]; i++) v[i] ^= ((a[i] > a[y]) ^ (a[i] > a[x]));
for (int i = y - 1; id[i] == id[y]; i--) v[i] ^= ((a[i] > a[y]) ^ (a[i] > a[x]));
for (int i = x; id[i] == id[x]; i++) if (a[y] > a[i]) v[y] ^= 1;
for (int i = y - 1; id[i] == id[y]; i--) if (a[y] > a[i]) v[y] ^= 1;
for (int i = x + 1; id[i] == id[x]; i++) if (a[x] > a[i]) v[x] ^= 1;
for (int i = y; id[i] == id[y]; i--) if (a[x] > a[i]) v[x] ^= 1;
for (int i = id[x] + 1; i < id[y]; i++) v[x] ^= cg(i, a[x]), v[y] ^= cg(i, a[y]);
mdf(id[x], a[x], a[y]), mdf(id[y], a[y], a[x]);
swap(a[x], a[y]), swap(pos[a[x]], pos[a[y]]), swap(v[x], v[y]);
psup(id[x]), psup(id[y]);
}
int calc() {
int p = cnt;
while (p >= 1 && !c[p]) p--;
if (!p) return 1;
psdw(p);
int x = R[p];
while (x >= L[p] && !v[x]) x--;
psup(p);
return x + 1;
}
int main() {
n = read(), m = read(), B = min(n, int(sqrt(n) / __lg(n + 1) + 1));
rep(i, 1, n) a[i] = read(), pos[a[i]] = i;
drep(i, n, 1) v[i] = qry(a[i]), upd(a[i]);
build();
rep(i, 1, m) {
int x = read(), y = read();
if (x > y) swap(x, y);
work(x, y);
printf("%d\n", calc());
}
return 0;
}