#include <bits/stdc++.h>
#define tree TrEe
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0;
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    return x;
}


constexpr int N = 100005, B = 2005;

int n, q;
int bl[N], br[N], blk[N], bc = 1;

struct node {
    int ls, rs, t, v, r0, r1;
}tree[10000005];

#define ls(p) tree[p].ls
#define rs(p) tree[p].rs
#define t(p)  tree[p].t
#define v(p)  tree[p].v
#define r0(p) tree[p].r0
#define r1(p) tree[p].r1

int tot = 0;

inline int new_n() {
    return ++tot;
}

inline void rev(int p) {
    std::swap(r0(p), r1(p));
    t(p) ^= 1;
}

inline void pushup(int p) {
    r0(p) = std::max(r0(ls(p)), r0(rs(p)));
    r1(p) = std::max(r1(ls(p)), r1(rs(p)));
    v(p)  = v(ls(p)) ^ v(rs(p));
}

inline void pushdown(int p) {
    if (t(p)) {
        if (ls(p)) rev(ls(p));
        if (rs(p)) rev(rs(p));
        t(p) = 0;
    }
}

inline void ins(int p, int _l, int _r, int x, int v) {
    if (x > _r || x < _l)
        return;
    if (_l == _r) {
        v(p) = 1;
        (v ? r1(p) : r0(p)) = _l;
        return;
    }
    pushdown(p);
    int mid = (_l + _r) >> 1;
    if (x <= mid) {
        if (!ls(p))
            ls(p) = new_n();
        ins(ls(p), _l, mid, x, v);
    } else {
        if (!rs(p))
            rs(p) = new_n();
        ins(rs(p), mid + 1, _r, x, v);
    }
    pushup(p);
}

inline void del(int p, int _l, int _r, int x) {
    if (x > _r || x < _l)
        return;
    if (_l == _r) {
        v(p) = 0;
        r0(p) = r1(p) = 0;
        return;
    }
    pushdown(p);
    int mid = (_l + _r) >> 1;
    if (x <= mid) 
        del(ls(p), _l, mid, x);
    else
        del(rs(p), mid + 1, _r, x);
    pushup(p);
}

inline void rev_lr(int p, int _l, int _r, int l, int r) {
    if (!p) 
        return;
    if (l > _r || r < _l) 
        return;
    if (l <= _l && _r <= r) {
        rev(p);
        return;
    }
    pushdown(p);
    int mid = (_l + _r) >> 1;
    rev_lr(ls(p), _l, mid, l, r);
    rev_lr(rs(p), mid + 1, _r, l, r);
    pushup(p);
}

inline int get_v(int p, int _l, int _r, int x) {
    if (!p) 
        return 0;
    if (_l == _r) 
        return v(p);
    int mid = (_l + _r) >> 1;
    if (x + 1 <= mid)
        return get_v(ls(p), _l, mid, x) ^ v(rs(p));
    else 
        return get_v(rs(p), mid + 1, _r, x);
}

int rt[N];
int a[N], pos[N];

inline int get_01(int x) {
    int res = 0;
    for (int i = 1; i <= blk[a[x] - 1] - 1; i++)
        res ^= get_v(rt[i], 1, n, x);
    for (int i = bl[blk[a[x] - 1]]; i <= a[x] - 1; i++)
        if (pos[i] > x) 
            res ^= 1;
    // std::cout << res << '\n';
    return res;
}

inline int get_ans() {
    int ans = 0;
    for (int i = 1; i <= bc; i++)
        ans = std::max(ans, r1(rt[i]) + 1);
    return ans;
}


int main() {
    freopen("perotation.in", "r", stdin);
    freopen("perotation.out", "w", stdout);
    std::cin.tie(0)->sync_with_stdio(0);
    // std::cin >> n >> q;
    n = read(), q = read();
    for (int &i = bc; (i - 1) * B + 1 <= n; i++) {
        bl[i] = (i - 1) * B + 1;
        br[i] = std::min(i * B, n);
        for (int j = bl[i]; j <= br[i]; j++)
            blk[j] = i;
    }
    --bc;
    for (int i = 1; i <= bc; i++) 
        rt[i] = new_n();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (int i = 1; i <= n; i++)
        pos[a[i]] = i;
    for (int i = n; i >= 1; i--) 
        ins(rt[blk[a[i]]], 1, n, i, (i == n ? 0 : get_01(i)));
    // std::cout << tot << '\n';
    int x, y;
    while (q--) {
        // std::cin >> x >> y;
        x = read(), y = read();
        if (x > y)
            std::swap(x, y);
        int l = std::min(a[x], a[y]) + 1, r = std::max(a[x], a[y]) - 1;
        if (l <= r) {
            if (blk[l] == blk[r]) {
                for (int i = l; i <= r; i++) 
                    if (pos[i] >= x && pos[i] <= y)
                        rev_lr(rt[blk[i]], 1, n, pos[i], pos[i]);
            } else {
                for (int i = l; i <= br[blk[l]]; i++) 
                    if (pos[i] >= x && pos[i] <= y)
                        rev_lr(rt[blk[i]], 1, n, pos[i], pos[i]);
                for (int i = blk[l] + 1; i <= blk[r] - 1; i++)
                    rev_lr(rt[i], 1, n, x, y);
                for (int i = bl[blk[r]]; i <= r; i++)
                    if (pos[i] >= x && pos[i] <= y)
                        rev_lr(rt[blk[i]], 1, n, pos[i], pos[i]);
            }
        }
        del(rt[blk[a[x]]], 1, n, x);
        del(rt[blk[a[y]]], 1, n, y);
        std::swap(pos[a[x]], pos[a[y]]);
        std::swap(a[x], a[y]);
        ins(rt[blk[a[y]]], 1, n, y, get_01(y));
        ins(rt[blk[a[x]]], 1, n, x, get_01(x));
        std::cout << get_ans() << '\n';
    }
}