#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

//typedef pair<long long int, long long int> P;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

int a[110000];

int main(){
	
	int N;
	cin >> N;
	
	for(int i = 0; i < N; i++){
		cin >> a[i];
	}
	
	map<long long int, long long int> m;
	int cnt = 0;
	
	vector<int> v;
	
	for(int i = 0; i < N; i++){
		m[a[i]]++;
		if(m[a[i]] == 0){
			cnt++;
		}else if(m[a[i]] == 1){
			cnt--;
		}
		m[a[N - i - 1]]--;
		if(m[a[N - i - 1]] == 0){
			cnt++;
		}else if(m[a[N - i - 1]] == -1){
			cnt--;
		}
		if(cnt == 0){
			v.push_back(i + 1);
		}
	}
	
	for(int i = 0; i < v.size() - 1; i++){
		cout << v[i] << " ";
	}
	cout << v[v.size() - 1] << 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
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

//typedef pair<long long int, long long int> P;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

int a[110000];

int main(){
	
	int N;
	cin >> N;
	
	for(int i = 0; i < N; i++){
		cin >> a[i];
	}
	
	map<long long int, long long int> m;
	int cnt = 0;
	
	vector<int> v;
	
	for(int i = 0; i < N; i++){
		m[a[i]]++;
		if(m[a[i]] == 0){
			cnt++;
		}else if(m[a[i]] == 1){
			cnt--;
		}
		m[a[N - i - 1]]--;
		if(m[a[N - i - 1]] == 0){
			cnt++;
		}else if(m[a[N - i - 1]] == -1){
			cnt--;
		}
		if(cnt == 0){
			v.push_back(i + 1);
		}
	}
	
	for(int i = 0; i < v.size() - 1; i++){
		cout << v[i] << " ";
	}
	cout << v[v.size() - 1] << endl;
	
	
	return 0;
}


```