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

int main() {
	int N;
	cin >> N;
	
	vector< int > a(N);
	for (int i=0; i<N; ++i) cin >> a[i];
	
	int L = 0, R = N-1, sum = 0;
	
	map< int, int > cnt;
	
	vector< int > ans;
	
	while (L < N) {
		if (a[L] != a[R]) {
			if (cnt[a[R]] == 0) ++sum;
			if (cnt[a[L]] == 0) ++sum;
			
			if (cnt[a[R]] == -1) --sum;
			if (cnt[a[L]] == 1) --sum;
			
			++cnt[a[R]];
			--cnt[a[L]];
		}
		
		if (sum == 0) ans.push_back(L+1);
		
		++L;
		--R;
	}
	
	int m = ans.size();
	for (int i=0; i<m; ++i) cout << ans[i] << (i<m-1? " " : "\n");
}

### Prompt

Your challenge is to write 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;

int main() {
	int N;
	cin >> N;
	
	vector< int > a(N);
	for (int i=0; i<N; ++i) cin >> a[i];
	
	int L = 0, R = N-1, sum = 0;
	
	map< int, int > cnt;
	
	vector< int > ans;
	
	while (L < N) {
		if (a[L] != a[R]) {
			if (cnt[a[R]] == 0) ++sum;
			if (cnt[a[L]] == 0) ++sum;
			
			if (cnt[a[R]] == -1) --sum;
			if (cnt[a[L]] == 1) --sum;
			
			++cnt[a[R]];
			--cnt[a[L]];
		}
		
		if (sum == 0) ans.push_back(L+1);
		
		++L;
		--R;
	}
	
	int m = ans.size();
	for (int i=0; i<m; ++i) cout << ans[i] << (i<m-1? " " : "\n");
}

```