#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for (ll i = 0, i##_len = (n); i < i##_len; i++)
#define ALL_OF(v) (v).begin(), (v).end()

int main() {

    ll n; cin >> n;
    vector<ll> a(n);
    REP(i, n) cin >> a[i];

    auto unq = a;
    sort(ALL_OF(unq));
    unq.erase(unique(ALL_OF(unq)), unq.end());
    for (ll &x : a) x = lower_bound(ALL_OF(unq), x) - unq.begin();
    ll diff = 0;
    vector<ll> dp(n, 0), dq(n, 0);
    vector<ll> ans;
    REP(i, n) {
        ll r = n-1-i;
        if (a[i] == a[r]) {
            int si = dp[a[i]] == dq[a[i]];
            dp[a[i]]++;
            dq[a[r]]++;
            diff += (dp[a[i]] == dq[a[i]]) - si;
        } else {
            int si = dp[a[i]] == dq[a[i]];
            int sr = dp[a[r]] == dq[a[r]];
            dp[a[i]]++;
            dq[a[r]]++;
            diff += (dp[a[i]] == dq[a[i]]) - si;
            diff += (dp[a[r]] == dq[a[r]]) - sr;
        }
        if (diff == 0) {
            ans.push_back(i + 1);
        }
    }

    REP(i, ans.size()) cout << ans[i] << " \n"[i+1==ans.size()];

}

### Prompt

Your challenge is to write a CPP solution to 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 ll = long long;
#define REP(i,n) for (ll i = 0, i##_len = (n); i < i##_len; i++)
#define ALL_OF(v) (v).begin(), (v).end()

int main() {

    ll n; cin >> n;
    vector<ll> a(n);
    REP(i, n) cin >> a[i];

    auto unq = a;
    sort(ALL_OF(unq));
    unq.erase(unique(ALL_OF(unq)), unq.end());
    for (ll &x : a) x = lower_bound(ALL_OF(unq), x) - unq.begin();
    ll diff = 0;
    vector<ll> dp(n, 0), dq(n, 0);
    vector<ll> ans;
    REP(i, n) {
        ll r = n-1-i;
        if (a[i] == a[r]) {
            int si = dp[a[i]] == dq[a[i]];
            dp[a[i]]++;
            dq[a[r]]++;
            diff += (dp[a[i]] == dq[a[i]]) - si;
        } else {
            int si = dp[a[i]] == dq[a[i]];
            int sr = dp[a[r]] == dq[a[r]];
            dp[a[i]]++;
            dq[a[r]]++;
            diff += (dp[a[i]] == dq[a[i]]) - si;
            diff += (dp[a[r]] == dq[a[r]]) - sr;
        }
        if (diff == 0) {
            ans.push_back(i + 1);
        }
    }

    REP(i, ans.size()) cout << ans[i] << " \n"[i+1==ans.size()];

}

```