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

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; ++i) cin >> A[i];
  int d = 0;
  map<int,int> D;
  vector<int> K;
  for(int k = 0; k < N; ++k){
    d -= abs(D[A[k]]);
    ++D[A[k]];
    d += abs(D[A[k]]);
    d -= abs(D[A[N-1-k]]);
    --D[A[N-1-k]];
    d += abs(D[A[N-1-k]]);
    if(!d) K.push_back(k+1);
    // cerr << k << " " << d << endl;
  }
  for(size_t i = 0; i < K.size(); ++i)
    cout << K[i] << (i+1 < K.size() ? " " : "\n");
}


### Prompt

Construct a cpp code solution to the problem outlined:

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 <vector>
#include <map>
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; ++i) cin >> A[i];
  int d = 0;
  map<int,int> D;
  vector<int> K;
  for(int k = 0; k < N; ++k){
    d -= abs(D[A[k]]);
    ++D[A[k]];
    d += abs(D[A[k]]);
    d -= abs(D[A[N-1-k]]);
    --D[A[N-1-k]];
    d += abs(D[A[N-1-k]]);
    if(!d) K.push_back(k+1);
    // cerr << k << " " << d << endl;
  }
  for(size_t i = 0; i < K.size(); ++i)
    cout << K[i] << (i+1 < K.size() ? " " : "\n");
}


```