#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;

const int MOD = 40;
const int INF = 1e9;
const ll LINF = 1e18;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const int ddx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int ddy[] = {0, 1, 1, 1, 0, -1, -1, -1};

ll gcd(ll a, ll b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

int extgcd(int a, int b, int& x, int&y) {
    int d = a;
    if(b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else {
        x = 1;
        y = 0;
    }
    return d;
}

int inv(int a) {
    int x, y;
    extgcd(a, MOD, x, y);
    return (x + MOD) % MOD;
}

struct modint {
    int val;

    modint() {
        val = 0;
    }
    modint(int n) {
        val = n % MOD;
    }

    modint &operator=(const modint &x) {
        val = x.val;
        return *this;
    }
    bool operator==(const modint &rhs) const {return val == rhs.val;}
    modint operator+(const modint &rhs) const {return modint((val + rhs.val + MOD) % MOD);}
    modint operator-(const modint &rhs) const {return modint((val + MOD - rhs.val) % MOD);}
    modint operator*(const modint &rhs) const {return modint((int)((ll)val * rhs.val % MOD));}
    modint operator/(const modint &rhs) const {return modint((int)((ll)val * inv(rhs.val) % MOD));}
    modint &operator+=(const modint &rhs) {
        val = (val + rhs.val + MOD) % MOD;
        return *this;
    }
    modint &operator-=(const modint &rhs) {
        val = (val + MOD- rhs.val) % MOD;
        return *this;
    }
    modint &operator*=(const modint &rhs) {
        val = (int)((ll)val * rhs.val % MOD);
        return *this;
    }
    modint &operator/=(const modint &rhs) {
        val = (int)((ll)val * inv(rhs.val) % MOD);
        return *this;
    }
};

struct unitree {
    int *par, *rank, *sz;

    unitree(int n) {
        par = new int[n];
        rank = new int[n];
        sz = new int[n];
        for(int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
            sz[i] = 1;
        }
    }

    int root(int x) {
        if(par[x] == x) return x;
        else return par[x] = root(par[x]);
    }

    void merge(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(rank[x] < rank[y]) {
            par[x] = y;
            sz[y] += sz[x];
        }else {
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
            sz[x] += sz[y];
        }
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int siz(int x) {
        return sz[root(x)];
    }
};

int n;
ll k, *a, *f;

bool check(ll mid) {
    ll tmp = 0;
    rep(i, n) {
        if(a[i] * f[i] <= mid) continue;
        tmp += a[i] - mid / f[i];
    }
    return tmp > k;
}

ll bin(ll left, ll right) {
    while(right - left > 1) {
        ll mid = (left + right) / 2;
        if(check(mid)) left = mid;
        else right = mid;
    }
    return left;
}

struct vect {
    ll x, y;
    vect() {
        x = 0;
        y = 0;
    }
    vect(ll x, ll y) {
        this->x = x;
        this->y = y;
    }

    int posi() const {
        if(x == 0 && y == 0) exit(1);
        if(x > 0 && y == 0) return 0;
        if(x > 0 && y > 0) return 1;
        if(x == 0 && y > 0) return 2;
        if(x < 0 && y > 0) return 3;
        if(x < 0 && y == 0) return 4;
        if(x < 0 && y < 0) return 5;
        if(x == 0 && y < 0) return 6;
        if(x > 0 && y < 0) return 7;
    }

    int posi(const vect& v) const {
        ll s = x * v.y - y * v.x;
        ll c = x * v.x + y * v.y;
        if(s == 0 && c == 0) exit(1);
        if(s == 0 && c > 0) return 0;
        if(s > 0 && c > 0) return 1;
        if(s > 0 && c == 0) return 2;
        if(s > 0 && c < 0) return 3;
        if(s == 0 && c < 0) return 4;
        if(s < 0 && c < 0) return 5;
        if(s < 0 && c == 0) return 6;
        if(s < 0 && c > 0) return 7;
    }

    bool operator<(const vect& rhs) {
        int p1 = posi();
        int p2 = rhs.posi();
        if(p1 != p2) return p1 < p2;
        return rhs.x * y < x * rhs.y;
    }
};

signed main() {
    int n;
    cin >> n;
    int* a = new int[n];
    rep(i, n) cin >> a[i];
    multiset<int> f, b;
    vector<int> ans;
    for(int i = 0; i < n; i++) {
        auto itr = b.find(a[i]);
        if(itr == b.end()) f.insert(a[i]);
        else b.erase(itr);

        itr = f.find(a[n - 1 - i]);
        if(itr == f.end()) b.insert(a[n - 1 - i]);
        else f.erase(itr);

        if(f.empty() && b.empty()) ans.push_back(i + 1);
    }
    rep(i, ans.size()) printf("%d%c", ans[i], i == ans.size() - 1? '\n' : ' ');
}


### Prompt

Develop a solution in CPP to the problem described below:

problem

Given a sequence $ a_i $ of length $ N $. Output all integers $ K (1 \ le K \ le N) $ that satisfy the following conditions.

Condition: Well sorted $ a_1, \ cdots, a_K $ matches $ a_ {N-K + 1}, \ cdots, a_N $.





Example

Input

8
5 2 4 9 4 9 2 5


Output

1 2 4 6 7 8

### Response

```cpp
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;

const int MOD = 40;
const int INF = 1e9;
const ll LINF = 1e18;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const int ddx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int ddy[] = {0, 1, 1, 1, 0, -1, -1, -1};

ll gcd(ll a, ll b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

int extgcd(int a, int b, int& x, int&y) {
    int d = a;
    if(b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else {
        x = 1;
        y = 0;
    }
    return d;
}

int inv(int a) {
    int x, y;
    extgcd(a, MOD, x, y);
    return (x + MOD) % MOD;
}

struct modint {
    int val;

    modint() {
        val = 0;
    }
    modint(int n) {
        val = n % MOD;
    }

    modint &operator=(const modint &x) {
        val = x.val;
        return *this;
    }
    bool operator==(const modint &rhs) const {return val == rhs.val;}
    modint operator+(const modint &rhs) const {return modint((val + rhs.val + MOD) % MOD);}
    modint operator-(const modint &rhs) const {return modint((val + MOD - rhs.val) % MOD);}
    modint operator*(const modint &rhs) const {return modint((int)((ll)val * rhs.val % MOD));}
    modint operator/(const modint &rhs) const {return modint((int)((ll)val * inv(rhs.val) % MOD));}
    modint &operator+=(const modint &rhs) {
        val = (val + rhs.val + MOD) % MOD;
        return *this;
    }
    modint &operator-=(const modint &rhs) {
        val = (val + MOD- rhs.val) % MOD;
        return *this;
    }
    modint &operator*=(const modint &rhs) {
        val = (int)((ll)val * rhs.val % MOD);
        return *this;
    }
    modint &operator/=(const modint &rhs) {
        val = (int)((ll)val * inv(rhs.val) % MOD);
        return *this;
    }
};

struct unitree {
    int *par, *rank, *sz;

    unitree(int n) {
        par = new int[n];
        rank = new int[n];
        sz = new int[n];
        for(int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
            sz[i] = 1;
        }
    }

    int root(int x) {
        if(par[x] == x) return x;
        else return par[x] = root(par[x]);
    }

    void merge(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(rank[x] < rank[y]) {
            par[x] = y;
            sz[y] += sz[x];
        }else {
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
            sz[x] += sz[y];
        }
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int siz(int x) {
        return sz[root(x)];
    }
};

int n;
ll k, *a, *f;

bool check(ll mid) {
    ll tmp = 0;
    rep(i, n) {
        if(a[i] * f[i] <= mid) continue;
        tmp += a[i] - mid / f[i];
    }
    return tmp > k;
}

ll bin(ll left, ll right) {
    while(right - left > 1) {
        ll mid = (left + right) / 2;
        if(check(mid)) left = mid;
        else right = mid;
    }
    return left;
}

struct vect {
    ll x, y;
    vect() {
        x = 0;
        y = 0;
    }
    vect(ll x, ll y) {
        this->x = x;
        this->y = y;
    }

    int posi() const {
        if(x == 0 && y == 0) exit(1);
        if(x > 0 && y == 0) return 0;
        if(x > 0 && y > 0) return 1;
        if(x == 0 && y > 0) return 2;
        if(x < 0 && y > 0) return 3;
        if(x < 0 && y == 0) return 4;
        if(x < 0 && y < 0) return 5;
        if(x == 0 && y < 0) return 6;
        if(x > 0 && y < 0) return 7;
    }

    int posi(const vect& v) const {
        ll s = x * v.y - y * v.x;
        ll c = x * v.x + y * v.y;
        if(s == 0 && c == 0) exit(1);
        if(s == 0 && c > 0) return 0;
        if(s > 0 && c > 0) return 1;
        if(s > 0 && c == 0) return 2;
        if(s > 0 && c < 0) return 3;
        if(s == 0 && c < 0) return 4;
        if(s < 0 && c < 0) return 5;
        if(s < 0 && c == 0) return 6;
        if(s < 0 && c > 0) return 7;
    }

    bool operator<(const vect& rhs) {
        int p1 = posi();
        int p2 = rhs.posi();
        if(p1 != p2) return p1 < p2;
        return rhs.x * y < x * rhs.y;
    }
};

signed main() {
    int n;
    cin >> n;
    int* a = new int[n];
    rep(i, n) cin >> a[i];
    multiset<int> f, b;
    vector<int> ans;
    for(int i = 0; i < n; i++) {
        auto itr = b.find(a[i]);
        if(itr == b.end()) f.insert(a[i]);
        else b.erase(itr);

        itr = f.find(a[n - 1 - i]);
        if(itr == f.end()) b.insert(a[n - 1 - i]);
        else f.erase(itr);

        if(f.empty() && b.empty()) ans.push_back(i + 1);
    }
    rep(i, ans.size()) printf("%d%c", ans[i], i == ans.size() - 1? '\n' : ' ');
}


```