#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i = 0;i < n;++i) {
        cin>>a[i];
    }
    map<int,int> mp;
    set<int> cnt;
    vector<int> ans;
    for(int i = 0;i < n;++i) {
        mp[a[i]]++;
        if(mp[a[i]]==1)cnt.insert(a[i]);
        if(mp[a[i]]==0)cnt.erase(a[i]);

        mp[a[n-1-i]]--;
        if(mp[a[n-1-i]]==0)cnt.erase(a[n-1-i]);
        if(mp[a[n-1-i]]==-1)cnt.insert(a[n-1-i]);

        if(cnt.size()==0)ans.emplace_back(i+1);
    }

    for(int i = 0;i < ans.size()-1;++i) {
        cout<<ans[i]<<" ";
    }
    cout<<n<<endl;

    return 0;
}


### Prompt

Please formulate a cpp solution to the following problem:

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;
using ll = long long;

int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i = 0;i < n;++i) {
        cin>>a[i];
    }
    map<int,int> mp;
    set<int> cnt;
    vector<int> ans;
    for(int i = 0;i < n;++i) {
        mp[a[i]]++;
        if(mp[a[i]]==1)cnt.insert(a[i]);
        if(mp[a[i]]==0)cnt.erase(a[i]);

        mp[a[n-1-i]]--;
        if(mp[a[n-1-i]]==0)cnt.erase(a[n-1-i]);
        if(mp[a[n-1-i]]==-1)cnt.insert(a[n-1-i]);

        if(cnt.size()==0)ans.emplace_back(i+1);
    }

    for(int i = 0;i < ans.size()-1;++i) {
        cout<<ans[i]<<" ";
    }
    cout<<n<<endl;

    return 0;
}


```