#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#define pb push_back
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
const int N = (int)3e5 + 7;
int valid(int n, int inputSeq[]) {
int cnt = 1, start = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] == cnt) {
start = i;
break;
}
}
for (int i = start; i < n; i++) {
if (inputSeq[i] != cnt) {
return 0;
}
cnt++;
}
for (int i = 0; i < start; i++) {
if (inputSeq[i] != cnt) {
return 0;
}
cnt++;
}
return 1;
}
//----------------------
int has[N], pos[N];
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int start = -1, mx = -1;
memset(pos, -1, sizeof pos);
for (int i = 0; i < n; i++) {
has[gondolaSeq[i]] = 1;
pos[gondolaSeq[i]] = i;
mx = max(mx, gondolaSeq[i]);
if (gondolaSeq[i] <= n) {
if (start != -1) continue;
start = i - gondolaSeq[i] + 1;
if (start < 0) start += n;
}
}
deque < int > ans, dq;
if (start == -1)
start = 0;
for (int i = n + 1; i <= mx; i++) {
if (has[i]) {
ans.pb(pos[i] + 1);
while (!dq.empty()) {
ans.pb(dq.front());
dq.pop_front();
}
dq.clear();
} else {
dq.pb(i);
}
}
int i = 0;
for (int to : ans) {
replacementSeq[i++] = to;
}
return i;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
