思路 首先考虑 $n=1$ 的情况。由于长度为 $3$ 的排列只有 $3!$ 种情况，可以直接打表，得到所有情况下的答案。可以发现只有当每个元素的相邻元素都不是其前驱或后继时，这个排列才不存在 $LIS \le 1$ 的循环移位。这样可以得到一个 $O(1)$ 的做法。 接下来考虑 $n>1$ 的情况。这时候可以考虑类似于 $n=1$ 时的做法，即对于所有长度为 $2n+1$ 的排列，求出其所有的循环移位中 $LIS$ 的最大值。这个做法的时间复杂度为 $O((2n+1)!n)$，显然过不了。 注意到 $n$ 是一个很小的数，考虑利用这个性质来得到更优秀的算法。注意到 $n+1$ 个不同的数中，最长的子序列的长度不会超过 $n$。我们可以考虑将 $2n+1$ 的排列中的 $n+1$ 个不同的数划分为一些集合，使得每个集合中的数的子序列长度都不会超过 $n$。这样，我们就可以将 $2n+1$ 的排列分解为若干个这样的集合的并，每个集合中的数任意排列，这个排列的任意循环移位都不存在 $LIS>n$。 接下来考虑如何划分这些集合。我们可以考虑维护一个 $n+1$ 长度的序列，表示当前已经填入的集合的编号。当前的数可以放在哪个集合中呢？我们可以考虑枚举这个数能够和哪些集合中的数组成新的集合。如果能够组成一个新的集合，就将其加入序列中，继续处理下一个数。如果不能组成新的集合，就将当前序列中最后一个集合中的数删去，再次尝试将当前数加入序列中。如果最后序列中所有的数都无法和当前数组成新的集合，那么就开辟一个新的集合，将当前数加入其中。 这样的时间复杂度是 $O(2^nnm)$，

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, p[N], ans[N];
int fa[N], sz[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (sz[x] > sz[y]) swap(x, y);
    fa[x] = y, sz[y] += sz[x];
    return true;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n * 2 + 1; ++i) scanf("%d", p + i);
    for (int i = 1; i <= n * 2 + 1; ++i) fa[i] = i, sz[i] = 1;
    int cnt = n + 1;
    for (int i = 1; i <= n * 2 + 1; ++i) {
        int l = max(1, i - n), r = min(n * 2 + 1, i + n);
        for (int j = l; j <= r; ++j) {
            if (p[i] < p[j]) merge(i, j);
        }
    }
    vector<vector<int>> G(cnt);
    vector<int> id(n * 2 + 1);
    iota(id.begin(), id.end(), 0);
    sort(id.begin() + 1, id.end(), [&](int x, int y) { return p[x] < p[y]; });
    for (int i = 1; i <= n * 2 + 1; ++i) {
        int x = find(id[i]), y = find(id[i - 1]);
        if (x != y) {
            merge(x, y);
            G[x].push_back(y), G[y].push_back(x);
        }
    }
    vector<vector<int>> all;
    vector<int> cur;
    auto dfs = [&](auto &dfs, int u, int fa) -> void {
        cur.push_back(u);
        bool flag = true;
        for (int v : G[u]) {
            if (v == fa) continue;
            flag = false;
            dfs(dfs, v, u);
        }
        if (flag) all.push_back(cur);
        cur.pop_back();
    };
    for (int i = 1; i <= cnt - 1; ++i) {
        if (find(i) == i) dfs(dfs, i, -1);
    }
    set<int> S;
    auto check = [&](int l, int r) -> bool {
        S.clear();
        for (int i = l; i <= r; ++i) {
            if (S.count(p[id[i]])) return false;
            S.insert(p[id[i]]);
        }
        return true;
    };
    for (int i = 1; i <= n * 2 + 1; ++i) {
        int l = i, r = min(n * 2 + 1, i + n - 1);
        if (check(l, r)) ans[0] = i - 1;
    }
    for (const auto &vec : all) {
        vector<int> pos;
        for (int x : vec) pos.push_back(x);
        sort(pos.begin(), pos.end());
        int sz = pos.size();
        for (int i = 0; i < sz; ++i) pos.push_back(pos[i] + cnt);
        for (int i = 0; i < sz; ++i) {
            int l = i, r = i + sz - 1;
            if (check(l, r)) ans[pos[i] - 1] = i;
        }
    }
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        swap(p[u], p[v]);
        for (int i = u - n; i <= u + n; ++i) {
            if (i <= 0 || i > n * 2 + 1) continue;
            if (p[i] < p[u]) merge(i, u);
        }
        for (int i = v - n; i <= v + n; ++i) {
            if (i <= 0 || i > n * 2 + 1) continue;
            if (p[i] < p[v]) merge(i, v);
        }
        for (int i = u - n; i <= u + n; ++i) {
            if (i <= 0 || i > n * 2 + 1) continue;
            if (p[i] > p[u]) {
                int x = find(i), y = find(u);
                if (x != y) {
                    G[x].push_back(y), G[y].push_back(x);
                    merge(x, y);
                }
            }
        }
        for (int i = v - n; i <= v + n; ++i) {
            if (i <= 0 || i > n * 2 + 1) continue;
            if (p[i] > p[v]) {
                int x = find(i), y = find(v);
                if (x != y) {
                    G[x].push_back(y), G[y].push_back(x);
                    merge(x, y);
                }
            }
        }
        vector<vector<int>> new_all;
        vector<int> new_cur;
        auto new_dfs = [&](auto &dfs, int u, int fa) -> void {
            new_cur.push_back(u);
            bool flag = true;
            for (int v : G[u]) {
                if (v == fa) continue;
                flag = false;
                dfs(dfs, v, u);
            }
            if (flag) new_all.push_back(new_cur);
            new_cur.pop_back();
        };
        for (int i = 1; i <= cnt - 1; ++i) {
            if (find(i) == i) new_dfs(new_dfs, i, -1);
        }
        for (const auto &vec : new_all) {
            vector<int> pos;
            for (int x : vec) pos.push_back(x);
            sort(pos.begin(), pos.end());
            int sz = pos.size();
            for (int i = 0; i < sz; ++i) pos.push_back(pos[i] + cnt);
            for (int i = 0; i < sz; ++i) {
                int l = i, r = i + sz - 1;
                if (check(l, r)) ans[pos[i] - 1] = i;
            }
        }
        for (int i = u - n; i <= u + n; ++i) {
            if (i <= 0 || i > n * 2 + 1) continue;
            if (p[i] < p[u]) merge(i, u);
        }
        for (int i = v - n; i <= v + n; ++i) {
            if (i <= 0 || i > n * 2 + 1) continue;
            if (p[i] < p[v]) merge(i, v);
        }
    }
    for (int i = 0; i <= n * 2; ++i) {
        if (ans[i] == -1)
            printf("-1\n");
        else
            printf("%d\n", ans[i]);
    }
    return 0;
}