#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int INF = 1 << 30;

int N, A[100000];
map< int, int > latte, malta;
int diff;


int main() {

  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  bool first = false;

  for(int i = 0; i < N; i++) {
    int j = N - 1 - i;
    if(malta[A[i]] == latte[A[i]]) ++diff;
    latte[A[i]]++;
    if(malta[A[i]] == latte[A[i]]) --diff;
    if(malta[A[j]] == latte[A[j]]) ++diff;
    malta[A[j]]++;
    if(malta[A[j]] == latte[A[j]]) --diff;
    if(diff == 0) {
      if(first++) cout << " ";
      cout << i + 1;
    }
  }
  cout << endl;

}

### 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 int64 = long long;
const int INF = 1 << 30;

int N, A[100000];
map< int, int > latte, malta;
int diff;


int main() {

  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  bool first = false;

  for(int i = 0; i < N; i++) {
    int j = N - 1 - i;
    if(malta[A[i]] == latte[A[i]]) ++diff;
    latte[A[i]]++;
    if(malta[A[i]] == latte[A[i]]) --diff;
    if(malta[A[j]] == latte[A[j]]) ++diff;
    malta[A[j]]++;
    if(malta[A[j]] == latte[A[j]]) --diff;
    if(diff == 0) {
      if(first++) cout << " ";
      cout << i + 1;
    }
  }
  cout << endl;

}

```