#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n);
  for(Int i=0;i<n;i++) cin>>a[i];
  Int ok=0,x=0;
  map<Int, Int> m;
  for(Int i=0;i<n;i++){
    if(m[a[i]]++==0) ok++;
    if(m[a[i]]==0) ok--;
    if(m[a[n-(i+1)]]--==0) ok++;
    if(m[a[n-(i+1)]]==0) ok--;
    
    if(!ok){
      if(x) cout<<" ";
      x=1;
      cout<<i+1;
    }
  }
  cout<<endl;
  return 0;
}


### Prompt

Create a solution in cpp for 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;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n);
  for(Int i=0;i<n;i++) cin>>a[i];
  Int ok=0,x=0;
  map<Int, Int> m;
  for(Int i=0;i<n;i++){
    if(m[a[i]]++==0) ok++;
    if(m[a[i]]==0) ok--;
    if(m[a[n-(i+1)]]--==0) ok++;
    if(m[a[n-(i+1)]]==0) ok--;
    
    if(!ok){
      if(x) cout<<" ";
      x=1;
      cout<<i+1;
    }
  }
  cout<<endl;
  return 0;
}


```