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

void compress(vector<int> &a) {
	vector<int> sa; int i;
	for (i = 0; i < a.size(); i++) sa.push_back(a[i]);
	sort(sa.begin(), sa.end());
	sa.erase(unique(sa.begin(), sa.end()), sa.end());
	for (i = 0; i < a.size(); i++) a[i] = lower_bound(sa.begin(), sa.end(), a[i]) - sa.begin();
}

int n;
vector<int> a;
int cnt[100000];

int main() {
	int i;
	
	cin >> n;
	a.resize(n);
	for (i = 0; i < n; i++) cin >> a[i];
	compress(a);
	
	int nozeroCnt = 0;
	vector<int> ans;
	for (i = 0; i < n; i++) {
		if (cnt[a[i]] == -1) nozeroCnt--; if (cnt[a[i]] == 0) nozeroCnt++;
		cnt[a[i]]++;
		if (cnt[a[n - 1 - i]] == 1) nozeroCnt--; if (cnt[a[n - 1 - i]] == 0) nozeroCnt++;
		cnt[a[n - 1 - i]]--;
		if (nozeroCnt == 0) {
			ans.push_back(i + 1);
		}
	}
	
	for (i = 0; i < ans.size(); i++) {
		cout << ans[i];
		if (i + 1 < ans.size()) cout << " ";
	}
	cout << endl;
	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 <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void compress(vector<int> &a) {
	vector<int> sa; int i;
	for (i = 0; i < a.size(); i++) sa.push_back(a[i]);
	sort(sa.begin(), sa.end());
	sa.erase(unique(sa.begin(), sa.end()), sa.end());
	for (i = 0; i < a.size(); i++) a[i] = lower_bound(sa.begin(), sa.end(), a[i]) - sa.begin();
}

int n;
vector<int> a;
int cnt[100000];

int main() {
	int i;
	
	cin >> n;
	a.resize(n);
	for (i = 0; i < n; i++) cin >> a[i];
	compress(a);
	
	int nozeroCnt = 0;
	vector<int> ans;
	for (i = 0; i < n; i++) {
		if (cnt[a[i]] == -1) nozeroCnt--; if (cnt[a[i]] == 0) nozeroCnt++;
		cnt[a[i]]++;
		if (cnt[a[n - 1 - i]] == 1) nozeroCnt--; if (cnt[a[n - 1 - i]] == 0) nozeroCnt++;
		cnt[a[n - 1 - i]]--;
		if (nozeroCnt == 0) {
			ans.push_back(i + 1);
		}
	}
	
	for (i = 0; i < ans.size(); i++) {
		cout << ans[i];
		if (i + 1 < ans.size()) cout << " ";
	}
	cout << endl;
	return 0;
}

```