#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<ll,ll> pint;

int a[100001];
vector<int> v;
map<int,int> t;
int main(){
    int n;
    cin>>n;
    rep(i,n) cin>>a[i];
    int cnt=0;
    rep(i,n){
        if(a[i]==a[n-i-1]&&cnt==0) v.pb(i+1);
        else if(a[i]==a[n-i-1]&&cnt>=1) continue;
        else if(a[i]!=a[n-i-1]){
            ++t[a[i]];--t[a[n-i-1]];
            if(t[a[i]]==0) --cnt;
            else if(t[a[i]]==1) ++cnt;
            if(t[a[n-i-1]]==0) --cnt;
            else if(t[a[n-i-1]]==-1) ++cnt;
            if(cnt==0) v.pb(i+1);
        }
    }
    rep(i,v.size()){
        cout<<v[i]<<(i+1==v.size()?"":" ");
    }
    cout<<endl;
    return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<ll,ll> pint;

int a[100001];
vector<int> v;
map<int,int> t;
int main(){
    int n;
    cin>>n;
    rep(i,n) cin>>a[i];
    int cnt=0;
    rep(i,n){
        if(a[i]==a[n-i-1]&&cnt==0) v.pb(i+1);
        else if(a[i]==a[n-i-1]&&cnt>=1) continue;
        else if(a[i]!=a[n-i-1]){
            ++t[a[i]];--t[a[n-i-1]];
            if(t[a[i]]==0) --cnt;
            else if(t[a[i]]==1) ++cnt;
            if(t[a[n-i-1]]==0) --cnt;
            else if(t[a[n-i-1]]==-1) ++cnt;
            if(cnt==0) v.pb(i+1);
        }
    }
    rep(i,v.size()){
        cout<<v[i]<<(i+1==v.size()?"":" ");
    }
    cout<<endl;
    return 0;
}

```