#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int SIZE = 100000;

int main(){
  int n, a[SIZE];

  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",a+i);
  }

  map<int, int> b, e;
  vector<int> ans;
  
  int counter = 1000000000;
  
  for(int i=0;i<n;i++){
    if(b[a[i]] == e[a[i]]){
      counter--;
    }

    if(b[a[n-i-1]] == e[a[n-i-1]]){
      counter--;
    }

    
    b[a[i]]++;
    e[a[n-i-1]]++;

    if(b[a[i]] == e[a[i]]){
      counter++;
    }

    if(b[a[n-i-1]] == e[a[n-i-1]]){
      counter++;
    }

    if(counter == 1000000000){
      ans.push_back(i+1);
    }
  }

  for(int i=0;i<ans.size();i++){
    printf("%d%c",ans[i], " \n"[i+1==ans.size()]);
  }

  return 0;
}
  



### Prompt

Please provide a cpp coded solution 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 <cstdio>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int SIZE = 100000;

int main(){
  int n, a[SIZE];

  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",a+i);
  }

  map<int, int> b, e;
  vector<int> ans;
  
  int counter = 1000000000;
  
  for(int i=0;i<n;i++){
    if(b[a[i]] == e[a[i]]){
      counter--;
    }

    if(b[a[n-i-1]] == e[a[n-i-1]]){
      counter--;
    }

    
    b[a[i]]++;
    e[a[n-i-1]]++;

    if(b[a[i]] == e[a[i]]){
      counter++;
    }

    if(b[a[n-i-1]] == e[a[n-i-1]]){
      counter++;
    }

    if(counter == 1000000000){
      ans.push_back(i+1);
    }
  }

  for(int i=0;i<ans.size();i++){
    printf("%d%c",ans[i], " \n"[i+1==ans.size()]);
  }

  return 0;
}
  



```