#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <string>
#define SIZE 100005
#define INF 1000000005LL

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int n;
P A[SIZE];
int B[SIZE];
int C[SIZE];

int main()
{
	scanf("%d",&n);
	int a;
	for(int i=0;i<n;i++){
		scanf("%d",&a);
		A[i] = make_pair(a,i);
	}
	sort(A,A+n);
	int cnt=0;
	for(int i=0;i<n;i++){
		B[A[i].second] = cnt;
		if(A[i].first < A[i+1].first)cnt++;
	}
	int c=0;
	bool b=false;
	for(int i=0;i<n;i++){
		int f = B[i];
		int s = B[n-1-i];
		if(f!=s){
			C[f]++;
			C[s]--;
			if(C[f] == 0)c--;
			if(C[s] == 0)c--;
			if(C[f] == 1)c++;
			if(C[s] == -1)c++;
		}
		if(c==0){
			if(!b)b=true;
			else printf(" ");
			printf("%d",i+1);
		}
	}
	printf("\n");
	return 0;
}


### Prompt

In cpp, your task is to solve 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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <string>
#define SIZE 100005
#define INF 1000000005LL

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int n;
P A[SIZE];
int B[SIZE];
int C[SIZE];

int main()
{
	scanf("%d",&n);
	int a;
	for(int i=0;i<n;i++){
		scanf("%d",&a);
		A[i] = make_pair(a,i);
	}
	sort(A,A+n);
	int cnt=0;
	for(int i=0;i<n;i++){
		B[A[i].second] = cnt;
		if(A[i].first < A[i+1].first)cnt++;
	}
	int c=0;
	bool b=false;
	for(int i=0;i<n;i++){
		int f = B[i];
		int s = B[n-1-i];
		if(f!=s){
			C[f]++;
			C[s]--;
			if(C[f] == 0)c--;
			if(C[s] == 0)c--;
			if(C[f] == 1)c++;
			if(C[s] == -1)c++;
		}
		if(c==0){
			if(!b)b=true;
			else printf(" ");
			printf("%d",i+1);
		}
	}
	printf("\n");
	return 0;
}


```