#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[]) {
for (int i = 0; i < n; i++) {
inputSeq[i]--;
}
int beg = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] < n) {
beg = (inputSeq[i] - i + n) % n;
}
}
if (beg != -1) {
for (int i = 0; i < n; i++) {
if (inputSeq[i] < n) {
if (inputSeq[i] != (beg + i) % n) {
return 0;
}
}
}
}
sort(inputSeq, inputSeq + n);
if (unique(inputSeq, inputSeq + n) - inputSeq != n) {
return 0;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
for (int i = 0; i < n; i++) {
gondolaSeq[i]--;
}
int beg = -1;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] < n) {
beg = (gondolaSeq[i] - i + n) % n;
}
}
vector<pair<int, int>> rpl;
for (int i = 0; i < n; i++) {
if (beg == -1) {
rpl.push_back(make_pair(gondolaSeq[i], i));
} else if (gondolaSeq[i] != (beg + i) % n) {
rpl.push_back(make_pair(gondolaSeq[i], (beg + i) % n));
}
}
sort(rpl.begin(), rpl.end());
int mx = 0;
set<int> opg;
for (int i = 0; i < n; i++) {
mx = max(mx, gondolaSeq[i]);
opg.insert(gondolaSeq[i]);
}
vector<int> ext;
for (int i = n; i <= mx; i++) {
if (!opg.count(i)) {
ext.push_back(i);
}
}
int ret = 0, j = 0;
for (int i = 0; i < (int)rpl.size(); i++) {
replacementSeq[ret++] = rpl[i].second + 1;
while (j < (int)ext.size() && ext[j] < rpl[i].first) {
replacementSeq[ret++] = ext[j] + 1;
j++;
}
}
return ret;
}
int countReplacement(int n, int inputSeq[]) {
return -3;
}
