#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 250005;
int poz[maxN];
int valid(int n, int inputSeq[]) {
for (int i = 1; i <= n; i++) {
int x = inputSeq[i];
if (poz[x]) {
return 0;
}
poz[x] = i;
}
for (int i = 1; i < n; i++) {
int diff = poz[i + 1] - poz[i];
if (diff < 0) {
diff += n;
}
if (diff != 1) {
return 0;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
vector <int> extras;
int root = -1;
for (int i = 1; i <= n; i++) {
int x = gondolaSeq[i - 1];
if (x > n) {
extras.push_back(x);
} else {
root = x;
}
poz[x] = i;
}
sort(extras.begin(), extras.end());
int p = 0, last = n + 1;
for (int i = 0; i < extras.size(); i++) {
int x = extras[i];
int trueNumber = (root + (poz[x] - poz[root] + n) % n) % n;
if (trueNumber == 0) {
trueNumber += n;
}
replacementSeq[p++] = trueNumber;
while (last < extras[i]) {
replacementSeq[p++] = last;
last++;
}
last++;
}
return p;
}
int countReplacement(int n, int inputSeq[])
{
return -3;
}
