#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b, ans;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    b = a;
    reverse(b.begin(), b.end());
    map<int,int> cnta, cntb;
    set<int> dif;
    for(int i=0;i<n;i++){
        if(a[i]!=b[i]){
            cnta[a[i]]++;
            cntb[b[i]]++;
            if(cnta[a[i]]==cntb[a[i]]) dif.erase(a[i]);
            else dif.insert(a[i]);
            if(cnta[b[i]]==cntb[b[i]]) dif.erase(b[i]);
            else dif.insert(b[i]);
        }
        if(dif.empty()){
            ans.push_back(i+1);
        }
    }
    for(int i=0;i<int(ans.size());i++){
        cout << ans[i] << " \n"[i+1==ans.size()];
    }
    return 0;
}


### 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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b, ans;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    b = a;
    reverse(b.begin(), b.end());
    map<int,int> cnta, cntb;
    set<int> dif;
    for(int i=0;i<n;i++){
        if(a[i]!=b[i]){
            cnta[a[i]]++;
            cntb[b[i]]++;
            if(cnta[a[i]]==cntb[a[i]]) dif.erase(a[i]);
            else dif.insert(a[i]);
            if(cnta[b[i]]==cntb[b[i]]) dif.erase(b[i]);
            else dif.insert(b[i]);
        }
        if(dif.empty()){
            ans.push_back(i+1);
        }
    }
    for(int i=0;i<int(ans.size());i++){
        cout << ans[i] << " \n"[i+1==ans.size()];
    }
    return 0;
}


```