#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int a[100010];
int b[100010];
map<int, int> m;
int main(){
    int N;
    cin >> N;

    for(int i = 0; i < N; ++i){
        cin >> a[i];
    }

    int ckaz = 0;
    bool check = false;
    for(int i = 0; i < N; ++i){
        if(a[i] != a[N-i-1]){
            if(m[a[i]] == -1) ckaz--;
            if(m[a[N-i-1]] == 1) ckaz--;
            if(m[a[i]] == 0) ckaz++;
            if(m[a[N-i-1]] == 0) ckaz++;
            m[a[i]]++;
            m[a[N-i-1]]--;
        }
        
        if(ckaz == 0){
            if(check){
                cout << " ";
            }
            check = true;
            cout << i+1;
        }
    }
    cout << endl;
}

### Prompt

Create a solution in Cpp for 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 <iostream>
#include <map>
#include <algorithm>
using namespace std;

int a[100010];
int b[100010];
map<int, int> m;
int main(){
    int N;
    cin >> N;

    for(int i = 0; i < N; ++i){
        cin >> a[i];
    }

    int ckaz = 0;
    bool check = false;
    for(int i = 0; i < N; ++i){
        if(a[i] != a[N-i-1]){
            if(m[a[i]] == -1) ckaz--;
            if(m[a[N-i-1]] == 1) ckaz--;
            if(m[a[i]] == 0) ckaz++;
            if(m[a[N-i-1]] == 0) ckaz++;
            m[a[i]]++;
            m[a[N-i-1]]--;
        }
        
        if(ckaz == 0){
            if(check){
                cout << " ";
            }
            check = true;
            cout << i+1;
        }
    }
    cout << endl;
}

```