#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int N = 3e5;
int bar[N];
int valid(int n, int a[])
{
return -1;
}
//----------------------
int replacement(int n, int a[], int ans[])
{
int pos, san = -1;
rep(i, 1, n+1)bar[i] = 1;
rep(i, 0, n) {
if (a[i] <= n)pos = i, san = a[i];
bar[a[i]] = 1;
}
vector<P> b;
if (san == -1) {
rep(i, 0, n)
b.push_back({a[i], i+1});
}
else {
int x = san+1;
if (x > n)x -= n;
while (x != san) {
int np = (pos+1)%n;
if (a[np] > n)b.push_back({a[np], x});
pos += 1, x += 1;
if (x > n)x -= n;
}
}
sort(all(b));
if (b.empty())return 0;
//for (auto i: b)cout << i.first << " " << i.second << nl;
int idx = 0;
ans[idx++] = b[0].second;
rep(i, b[0].second+1, b[0].first) {
if(bar[i])continue;
ans[idx++] = i;
}
int last = b[0].first+1;
rep(i, 1, sz(b)) {
ans[idx++] = b[i].second;
rep(j, last, b[i].first) {
if (bar[j])continue;
ans[idx++] = j;
}
last = b[i].first+1;
}
return idx;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
//1 2 3 4 5 6
//6 1 2 3 4 5
//5 6 1 2 3 4
//4 5 6 1 2 3
//3 4 5 6 1 2
//2 3 4 5 6 1
//1 2 3 8 9
