//----------------------------templates
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("tune=native")
    #pragma GCC target ("avx")
    //----------------------------
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll

    #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++)
    #define REP(i,n) for (int i=0;i<(int)(n);i++)
    #define REPS(i,n) for (int i=1;i<=(int)(n);i++)
    #define REPN(i,n) for (int i=(int)(n)-1;i>=0;i--)
    #define REPNS(i,n) for (int i=(int)(n);i>0;i--)

    #define I(n) scanf("%lld", &(n))
    #define LL(n) scanf("%lld", &(n))
    #define pb(n) push_back((n))
    #define mp(i,j) make_pair((i),(j))
    #define eb(i,j) emplace_back((i),(j))
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() )

    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())

    typedef vector<int> vi;
    typedef pair<int,int> pi;
    typedef vector<pi> vpi;
    typedef vector<vi> vvi;
    typedef vector<vpi> vvpi;
    typedef vector<vvi> vvvi;

    const int mod = 1000000007;

//--------------------------------------------
struct SegmentTree {
public:
    int n;
    vi node;

    SegmentTree(vi v) {
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, 0);
        REP(i,sz) node[i+n-1] = v[i];
        REPN(i,n-2) node[i] = max(node[2*i+1], node[2*i+2]);
    }
    void update(int k, int x){
        k += n-1;
        node[k] = x;
        while(k){
            k = (k-1)/2;
            node[k] = max(abs(node[2*k+1]),abs(node[2*k+2]));
        }
    }
    int getmax(int a, int b, int k=0, int l=0, int r=-1){
        if(r<0) r=n;
        if(r<=a || b<=l) return 0;
        if(a<=l && r<=b) return abs(node[k]);
        return max( getmax(a,b,2*k+1,l,(l+r)/2),getmax(a,b,2*k+2,(l+r)/2,r) );
    }

    int get(int k){ return node[k+n-1]; }
};

int n,a[100010];
map<int,int> zaatu;
signed main(){
    I(n);
    vi s(n+1);
    SegmentTree st(s);
    int zr = 1;
    REP(i,n) {
        I(a[i]);
        if(!zaatu[a[i]]) zaatu[a[i]] = zr++;
    }

    int r = n-1;
    bool init = true;
    REP(i,n){
        int vl = st.get(zaatu[a[i]]);
        st.update(zaatu[a[i]], vl + 1);
        int vr = st.get(zaatu[a[r-i]]);
        st.update(zaatu[a[r-i]], vr - 1);

        int cand = st.getmax(0,n);
        if(!cand){
            if(!init) printf(" ");
            init = false;
            printf("%lld", i+1);
        }
    }
    printf("\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
//----------------------------templates
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("tune=native")
    #pragma GCC target ("avx")
    //----------------------------
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll

    #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++)
    #define REP(i,n) for (int i=0;i<(int)(n);i++)
    #define REPS(i,n) for (int i=1;i<=(int)(n);i++)
    #define REPN(i,n) for (int i=(int)(n)-1;i>=0;i--)
    #define REPNS(i,n) for (int i=(int)(n);i>0;i--)

    #define I(n) scanf("%lld", &(n))
    #define LL(n) scanf("%lld", &(n))
    #define pb(n) push_back((n))
    #define mp(i,j) make_pair((i),(j))
    #define eb(i,j) emplace_back((i),(j))
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() )

    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())

    typedef vector<int> vi;
    typedef pair<int,int> pi;
    typedef vector<pi> vpi;
    typedef vector<vi> vvi;
    typedef vector<vpi> vvpi;
    typedef vector<vvi> vvvi;

    const int mod = 1000000007;

//--------------------------------------------
struct SegmentTree {
public:
    int n;
    vi node;

    SegmentTree(vi v) {
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, 0);
        REP(i,sz) node[i+n-1] = v[i];
        REPN(i,n-2) node[i] = max(node[2*i+1], node[2*i+2]);
    }
    void update(int k, int x){
        k += n-1;
        node[k] = x;
        while(k){
            k = (k-1)/2;
            node[k] = max(abs(node[2*k+1]),abs(node[2*k+2]));
        }
    }
    int getmax(int a, int b, int k=0, int l=0, int r=-1){
        if(r<0) r=n;
        if(r<=a || b<=l) return 0;
        if(a<=l && r<=b) return abs(node[k]);
        return max( getmax(a,b,2*k+1,l,(l+r)/2),getmax(a,b,2*k+2,(l+r)/2,r) );
    }

    int get(int k){ return node[k+n-1]; }
};

int n,a[100010];
map<int,int> zaatu;
signed main(){
    I(n);
    vi s(n+1);
    SegmentTree st(s);
    int zr = 1;
    REP(i,n) {
        I(a[i]);
        if(!zaatu[a[i]]) zaatu[a[i]] = zr++;
    }

    int r = n-1;
    bool init = true;
    REP(i,n){
        int vl = st.get(zaatu[a[i]]);
        st.update(zaatu[a[i]], vl + 1);
        int vr = st.get(zaatu[a[r-i]]);
        st.update(zaatu[a[r-i]], vr - 1);

        int cand = st.getmax(0,n);
        if(!cand){
            if(!init) printf(" ");
            init = false;
            printf("%lld", i+1);
        }
    }
    printf("\n");
}

```