#include <bits/stdc++.h> using namespace std; int n, a[300005], mp[300005], nxt[300005], pre[300005], cur, nb[300005]; int l[300005]; vector <int> ps[300005]; bool vis[300005]; // int df[300005]; // inline int upd(int l, int r, int x) // { // df[r + 1] -= x; // df[l] += x; // } int t[300005]; inline int qry(int x) { int res = 0; for (; x; x -= (x & (-x))) res += t[x]; return res; } inline void add(int x, int k) { for (; x <= n; x += (x & (-x))) t[x] += k; } inline void upd(int l, int r, int x) { // printf("upd: [%d, %d] %d\n", l, r, x); // fflush(stdout); add(r + 1, -x); add(l, x); // puts("success"); // fflush(stdout); } set <pair <int, int> > st; int lst; inline void del(int i) { if (lst == a[i]) { i = qry(i); } vis[i] = 1; lst = a[i]; if (a[i] != a[pre[i]] && pre[i]) { if (a[pre[i]] != a[nxt[i]]) { upd(l[pre[i]], pre[i], nxt[i] - i); } else { upd(l[pre[i]], pre[i], qry(nxt[i]) - i); } } ps[a[i]].pop_back(); // printf("cur:%d\n", cur); printf("%d ", i); // fflush(stdout); if (i == cur) cur = nxt[i]; nxt[pre[i]] = nxt[i]; pre[nxt[i]] = pre[i]; st.erase(make_pair(mp[a[i]], a[i])); mp[a[i]]--; if (mp[a[i]]) st.insert(make_pair(mp[a[i]], a[i])); // printf("done\n"); // fflush(stdout); } signed main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); if (a[i] == a[i - 1]) l[i] = l[i - 1]; else l[i] = i; mp[a[i]]++; nxt[i] = i + 1; pre[i] = i - 1; } cur = 1; for (int i = 1; i <= n; i++) { if (mp[i]) st.insert(make_pair(mp[i], i)); } if (st.rbegin() -> first > (n >> 1) + (n & 1)) { puts("-1"); return 0; } for (int i = n; i >= 1; i--) { ps[a[i]].push_back(i); if (a[i] == a[i + 1]) nb[i] = nb[i + 1]; else nb[i] = i + 1; } for (int i = 1; i <= n; i++) add(i, nb[i] - nb[i - 1]); for (int i = 1; i < n; i++) { // for (int j = 1; j <= n; j++) // { // if (!vis[j]) // printf("%d ", qry(j)); // else // printf(" "); // } // puts(""); // fflush(stdout); int remm = n - i + 1; if (st.rbegin() -> first == (remm >> 1) + (remm & 1)) { if (remm & 1) del(ps[st.rbegin() -> second].back()); else del(cur); } else { del(cur); } // puts(""); } printf("%d", cur); return 0; } /* 121 1212 */