#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

template <typename T> constexpr T inf;
template <> constexpr int inf<int> = 1e9;
template <> constexpr ll inf<ll> = 1e18;
template <> constexpr double inf<double> = 1e18;

int main() {
    int N;
    cin >> N;
    vector<int> a(N), xs;
    for(int i = 0; i < N; ++i) {
        cin >> a[i];
        xs.push_back(a[i]);
    }
    sort(begin(xs), end(xs));
    xs.erase(unique(begin(xs), end(xs)), end(xs));
    for(int i = 0; i < N; ++i) {
        a[i] = lower_bound(begin(xs), end(xs), a[i]) - begin(xs);
    }

    const int m = xs.size();
    int incorrect = 0;
    vector<int> cnt1(m), cnt2(m);
    vector<int> ans;
    for(int i = 0; i < N; ++i) {
        if(cnt1[a[i]] + 1 == cnt2[a[i]]) {
            incorrect -= 1;
        } else if(cnt1[a[i]] == cnt2[a[i]]) {
            incorrect += 1;
        }
        cnt1[a[i]] += 1;
        if(cnt2[a[N - i - 1]] + 1 == cnt1[a[N - i - 1]]) {
            incorrect -= 1;
        } else if(cnt1[a[N - i - 1]] == cnt2[a[N - i - 1]]) {
            incorrect += 1;
        }
        cnt2[a[N - i - 1]] += 1;

        if(incorrect == 0) {
            ans.push_back(i + 1);
        }
    }

    for(int i = 0; i < (int)ans.size(); ++i) {
        cout << ans[i] << " \n"[i + 1 == (int)ans.size()];
    }
}

### Prompt

Generate 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;
using pii = pair<int, int>;

template <typename T> constexpr T inf;
template <> constexpr int inf<int> = 1e9;
template <> constexpr ll inf<ll> = 1e18;
template <> constexpr double inf<double> = 1e18;

int main() {
    int N;
    cin >> N;
    vector<int> a(N), xs;
    for(int i = 0; i < N; ++i) {
        cin >> a[i];
        xs.push_back(a[i]);
    }
    sort(begin(xs), end(xs));
    xs.erase(unique(begin(xs), end(xs)), end(xs));
    for(int i = 0; i < N; ++i) {
        a[i] = lower_bound(begin(xs), end(xs), a[i]) - begin(xs);
    }

    const int m = xs.size();
    int incorrect = 0;
    vector<int> cnt1(m), cnt2(m);
    vector<int> ans;
    for(int i = 0; i < N; ++i) {
        if(cnt1[a[i]] + 1 == cnt2[a[i]]) {
            incorrect -= 1;
        } else if(cnt1[a[i]] == cnt2[a[i]]) {
            incorrect += 1;
        }
        cnt1[a[i]] += 1;
        if(cnt2[a[N - i - 1]] + 1 == cnt1[a[N - i - 1]]) {
            incorrect -= 1;
        } else if(cnt1[a[N - i - 1]] == cnt2[a[N - i - 1]]) {
            incorrect += 1;
        }
        cnt2[a[N - i - 1]] += 1;

        if(incorrect == 0) {
            ans.push_back(i + 1);
        }
    }

    for(int i = 0; i < (int)ans.size(); ++i) {
        cout << ans[i] << " \n"[i + 1 == (int)ans.size()];
    }
}

```