#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;cin>>N;
  int a[N];
  FOR(i,0,N)cin>>a[i];
  int b[N];
  FOR(i,0,N)b[N-i-1]=a[i];
  map<int, int> ma,mb;
  int diff=0;
  vector<int> ans;
  FOR(i,0,N){
    if(a[i]!=b[i]){
      diff+=2;
      ma[a[i]]++;
      mb[b[i]]++;
      if(mb[a[i]]>0){
        mb[a[i]]--;
        ma[a[i]]--;
        diff-=2;
      }
      if(ma[b[i]]>0){
        ma[b[i]]--;
        mb[b[i]]--;
        diff-=2;
      }
    }
    if(diff==0)ans.push_back(i+1);
  }
  FOR(i,0,ans.size()){
    if(i)cout<<" ";
    cout<<ans[i];
  }
  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 <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;cin>>N;
  int a[N];
  FOR(i,0,N)cin>>a[i];
  int b[N];
  FOR(i,0,N)b[N-i-1]=a[i];
  map<int, int> ma,mb;
  int diff=0;
  vector<int> ans;
  FOR(i,0,N){
    if(a[i]!=b[i]){
      diff+=2;
      ma[a[i]]++;
      mb[b[i]]++;
      if(mb[a[i]]>0){
        mb[a[i]]--;
        ma[a[i]]--;
        diff-=2;
      }
      if(ma[b[i]]>0){
        ma[b[i]]--;
        mb[b[i]]--;
        diff-=2;
      }
    }
    if(diff==0)ans.push_back(i+1);
  }
  FOR(i,0,ans.size()){
    if(i)cout<<" ";
    cout<<ans[i];
  }
  cout<<endl;
  return 0;
}

```