Gọi vị trí ~p~ là tốt nếu bỏ kí tự ở vị trí ~p~ thì dãy trở thành dãy đối xứng.

Thuật toán trâu ta có thể sử dụng ý tưởng đồ thị vô hướng với ~n~ đỉnh tương ứng với mỗi vị trí và với mỗi vị trí tốt ~p~, ta nối thêm ~\lfloor n/2\rfloor~ cạnh sao cho các cạnh nối 2 vị trí ~i~ và ~j~ phải bằng nhau. Cụ thể với ~1 \le p \le \lfloor \frac{n+1}{2}\rfloor~ thì ta nối cách cạnh từ ~(1 \longrightarrow p-1)~ tới ~(n \longrightarrow n-p+2)~ và các vị trí trong đoạn ~(p+1 \longrightarrow n-p+1)~ nối đối xứng với nhau. Cách nối tương tự nhưng ngược lại với ~\lfloor \frac{n+1}{2}\rfloor < p \le n~.

Sau khi nối cạnh, đơn giản ta chỉ cần gán mỗi thành phần liên thông một giá trị khác nhau. Thuật toán trên có độ phức tạp ~O(n\times m)~.

Để giảm độ phức tạp bài toán, ta cần giảm số cạnh cần nối. Ta có nhận xét rằng nếu hai vị trí tốt ~p~ và ~q~ thoả mãn ~1 \le p \le q \le \lfloor \frac{n+1}{2}\rfloor~, toàn bộ vị trí thuộc đoạn ~[p, q]~ đều tốt. Điều tương tự xảy ra với ~\lfloor \frac{n+1}{2}\rfloor < p \le q \le n~. Phần chứng minh để lại cho đọc giả.

Từ đó ta có thuật toán, với các vị trí tốt không vượt quá ~\lfloor \frac{n+1}{2}\rfloor~, tìm vị trí nhỏ nhất và lớn nhất, Ta chỉ cần quan tâm đến việc xử lý ~2~ vị trí tốt này vì sau khi xử lý thì những vị trị nằm giữa chúng đều sẽ được xử lý. Tương tự với các vị trí lớn hơn ~\lfloor \frac{n+1}{2}\rfloor~. Vậy thuật toán của ta chỉ còn ~O(n)~.

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)1e6+228;

struct DisjointSet
{
    vector<int> lab;
    int n;
    DisjointSet(int _n = 0)
    {
        n = _n;
        lab.assign(n+7, -1);
    }
    int Find(int u)
    {
        if(lab[u] < 0) return u;
        return lab[u] = Find(lab[u]);
    }
    void join(int u, int v)
    {
        u = Find(u), v = Find(v);
        if(u == v) return;
        if(lab[u] < lab[v]) swap(u, v);
        lab[v] += lab[u], lab[u] = v;
    }
}dsu;

int n, m, res[N], cnt[N];
bool mark[N];

int have(int l, int r)
{
    if(l > r) return false;
    return cnt[r] - cnt[l-1] > 0;
}

void solve()
{
    cin >> n >> m;
    for(int i=1; i<=m; ++i)
    {
        int p; cin >> p;
        mark[p] = true;
    }

    for(int i=1; i<=n; ++i) cnt[i] = cnt[i-1] + mark[i];

    dsu = DisjointSet(n);
    for(int i=1; i<=n; ++i)
    {
        if(have(1, i-1))
        {
            int p = n-1 - (i - 1) + 1;
            if(p + 1 < i && have(1, p)) dsu.join(i, p+1);
            if(p < i && have(p+1, i-1)) dsu.join(i, p);
        }

        if(have(i+1, n))
        {
            int p = n-1 - i + 1;
            if(p < i) dsu.join(i, p);
        }
    }

    int cur = 0;
    for(int i=1; i<=n; ++i)
    {
        int root = dsu.Find(i);
        if(res[root] == 0) res[root] = ++cur;
        res[i] = res[root];
    }

    for(int i=1; i<=n; ++i) cout << res[i] << " ";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(task".inp" , "r" , stdin);
    //freopen(task".out" , "w" , stdout);
    solve();
    return 0;
}