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

int n, num1[100005], num2[100005];

map<int,int> A, B;

signed main(){
  
  cin>>n;
  
  for(int i=0;i<n;i++){
    cin>>num1[i];
    num2[i] = num1[i];
  }
  
  reverse( num2, num2 + n );
  
  vector<int> ans;
  
  int cnt = 0;
  
  for(int i=0;i<n;i++){
    
    if( A[num1[i]] < B[num1[i]] ) cnt--;
    else cnt++;
    
    A[num1[i]]++;
    
    if( B[num2[i]] < A[num2[i]] ) cnt--;
    else cnt++;

    B[num2[i]]++;
    
    if( cnt == 0 ) ans.push_back( i + 1 );
    
  }
  
  for(int i=0;i<ans.size();i++){
    if(i) cout<<" ";
    cout<<ans[i];
  }
  cout<<endl;
  
  return 0;
}


### Prompt

Generate 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 n, num1[100005], num2[100005];

map<int,int> A, B;

signed main(){
  
  cin>>n;
  
  for(int i=0;i<n;i++){
    cin>>num1[i];
    num2[i] = num1[i];
  }
  
  reverse( num2, num2 + n );
  
  vector<int> ans;
  
  int cnt = 0;
  
  for(int i=0;i<n;i++){
    
    if( A[num1[i]] < B[num1[i]] ) cnt--;
    else cnt++;
    
    A[num1[i]]++;
    
    if( B[num2[i]] < A[num2[i]] ) cnt--;
    else cnt++;

    B[num2[i]]++;
    
    if( cnt == 0 ) ans.push_back( i + 1 );
    
  }
  
  for(int i=0;i<ans.size();i++){
    if(i) cout<<" ";
    cout<<ans[i];
  }
  cout<<endl;
  
  return 0;
}


```