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

int main(){
    int N;
    cin >> N;
    int nums[N];
    for(int i = 0; i < N; i++){
        cin >> nums[i];
    }
    int not_zero_count = 0;
    map<int, int> nums_map;
    string ans_string = "";
    for(int i = 0; i < N; i++){
        if(!nums_map[nums[i]]){
            not_zero_count++;
        }
        nums_map[nums[i]]++;
        if(!nums_map[nums[i]]){
            not_zero_count--;
        }
        if(!nums_map[nums[N - i - 1]]){
            not_zero_count++;
        }
        nums_map[nums[N - i - 1]]--;
        if(!nums_map[nums[N - i - 1]]){
            not_zero_count--;
        }
        if(!not_zero_count){
            ans_string += to_string(i + 1) + " ";
        }
    }
    ans_string.pop_back();
    cout << ans_string << endl;
}

### Prompt

Please provide a cpp coded solution 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 <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int main(){
    int N;
    cin >> N;
    int nums[N];
    for(int i = 0; i < N; i++){
        cin >> nums[i];
    }
    int not_zero_count = 0;
    map<int, int> nums_map;
    string ans_string = "";
    for(int i = 0; i < N; i++){
        if(!nums_map[nums[i]]){
            not_zero_count++;
        }
        nums_map[nums[i]]++;
        if(!nums_map[nums[i]]){
            not_zero_count--;
        }
        if(!nums_map[nums[N - i - 1]]){
            not_zero_count++;
        }
        nums_map[nums[N - i - 1]]--;
        if(!nums_map[nums[N - i - 1]]){
            not_zero_count--;
        }
        if(!not_zero_count){
            ans_string += to_string(i + 1) + " ";
        }
    }
    ans_string.pop_back();
    cout << ans_string << endl;
}

```