#include <bits/stdc++.h>

using i64 = long long;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> t;
    Fenwick(int n_ = 0) {
        init(n_);
    }
    void init(int n_) {
        n = n_;
        t.assign(n, T{});
    }
    void add(int p, const T &x) {
        for (++p; p <= n; p += p & -p) {
            t[p - 1] += x;
        }
    }
    T sum(int p) const {
        T x{};
        for (; p; p -= p & -p) {
            x += t[p - 1];
        }
        return x;
    }
    T rangeSum(int l, int r) const {
        return sum(r) - sum(l);
    }
};

constexpr int B = 500;

struct Block {
    std::vector<int> &a, &pos, &f;
    const int l = 0, r = 0;
    int sum = 0;
    std::vector<int> val, delta;
    Block(std::vector<int> &a_, std::vector<int> &pos_, std::vector<int> &f_, int l_, int r_)
        : a{a_}, pos{pos_}, f{f_}, l{l_}, r{r_}, sum{}, val(r - l), delta(r - l + 1) {
        std::copy(a.begin() + l, a.begin() + r, val.begin());
        std::sort(val.begin(), val.end());
        pull();
    }

    void pull() {
        sum = 0;
        for (int i = 0; i < r - l; ++i) {
            delta[i] = f[pos[val[i]]] ^ (i > 0 ? f[pos[val[i - 1]]] : 0);
            sum += delta[i];
        }
        delta[r - l] = 0;
    }
    void push() {
        for (int i = 0; i < r - l; ++i) {
            f[pos[val[i]]] = delta[i] ^ (i > 0 ? f[pos[val[i - 1]]] : 0);
        }
    }

    bool apply(int x) {
        int pos = std::upper_bound(val.begin(), val.end(), x) - val.begin();
        if (pos < r - l) {
            sum -= delta[pos] + delta[pos + 1];
            delta[pos] ^= 1;
            delta[pos + 1] ^= 1;
            sum += delta[pos] + delta[pos + 1];
        }
        return pos & 1;
    }
    void replace(int x, int y) {
        val.erase(std::lower_bound(val.begin(), val.end(), x));
        val.insert(std::upper_bound(val.begin(), val.end(), y), y);
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, q;
    std::cin >> n >> q;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        --a[i];
    }

    Fenwick<int> fen(n);
    std::vector<int> pos(n), f(n);
    for (int i = n - 1; i >= 0; --i) {
        pos[a[i]] = i;
        f[i] = fen.sum(a[i]) & 1;
        fen.add(a[i], 1);
    }

    std::vector<Block> block;
    for (int l = 0, r; l < n; l = r) {
        r = std::min(l + B, n);
        block.emplace_back(a, pos, f, l, r);
    }

    auto rangeApply = [&](int l, int r, int x, int y) {
        for (int i = l; i < r; ++i) {
            f[i] ^= (x < a[i]) ^ (y < a[i]);
        }
    };
    auto rangeQuery = [&](int l, int r, int x) {
        bool res = 0;
        for (int i = l; i < r; ++i) {
            res ^= a[i] < x;
        }
        return res;
    };
    auto modify = [&](int x, int y) {
        if (x / B == y / B) {
            block[x / B].push();

            rangeApply(x + 1, y, a[x], a[y]);
            f[x] ^= rangeQuery(x, y + 1, a[x]);
            f[y] ^= rangeQuery(x, y + 1, a[y]);

            std::swap(a[x], a[y]);
            std::swap(pos[a[x]], pos[a[y]]);
            std::swap(f[x], f[y]);

            block[x / B].pull();
        } else {
            block[x / B].push();
            block[y / B].push();

            int xr = (x / B + 1) * B, yl = y / B * B;
            rangeApply(x + 1, xr, a[x], a[y]);
            rangeApply(yl, y, a[x], a[y]);
            for (int i = x / B + 1; i < y / B; ++i) {
                f[x] ^= block[i].apply(a[x]);
                f[y] ^= block[i].apply(a[y]);
            }
            f[x] ^= rangeQuery(x, xr, a[x]);
            f[x] ^= rangeQuery(yl, y + 1, a[x]);
            f[y] ^= rangeQuery(x, xr, a[y]);
            f[y] ^= rangeQuery(yl, y + 1, a[y]);
            block[x / B].replace(a[x], a[y]);
            block[y / B].replace(a[y], a[x]);

            std::swap(a[x], a[y]);
            std::swap(pos[a[x]], pos[a[y]]);
            std::swap(f[x], f[y]);

            block[x / B].pull();
            block[y / B].pull();
        }
    };
    auto query = [&]() -> int {
        int id = (n - 1) / B;
        while (id >= 0 && block[id].sum == 0) {
            --id;
        }
        if (id == -1) {
            return 0;
        }
        block[id].push();
        int pos = std::min((id + 1) * B, n);
        while (f[pos - 1] == 0) {
            --pos;
        }
        return pos;
    };

    while (q--) {
        int x, y;
        std::cin >> x >> y;
        --x, --y;
        std::tie(x, y) = std::minmax({x, y});
        modify(x, y);
        std::cout << query() + 1 << "\n";
    }
    
    return 0;
}