#include "gondola.h"
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
int valid(int n, int inputSeq[]) {
for (int i = 0; i < n; i++)
inputSeq[i]--;
unordered_set<int> seen;
int startIdx = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] < n && startIdx == -1) {
startIdx = i;
}
if (seen.count(inputSeq[i]))
return 0;
seen.insert(inputSeq[i]);
}
if (startIdx == -1) {
return 1;
}
seen.clear();
int g = inputSeq[startIdx];
for (int i = 0; i < n; i++) {
int idx = (i + startIdx) % n;
if (inputSeq[idx] < n && inputSeq[idx] != g) {
return 0;
}
g = (g + 1) % n;
}
return 1;
}
int replacement(int n, int inputSeq[], int replacementSeq[])
{
for (int i = 0; i < n; i++)
inputSeq[i]--;
int startIdx = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] < n) {
startIdx = i;
break;
}
}
vector<pair<int, int>> br;
int g;
if (startIdx == -1) {
g = 0;
startIdx = 0;
} else {
g = inputSeq[startIdx];
}
for (int i = 0; i < n; i++) {
int idx = (i + startIdx) % n;
if (inputSeq[idx] >= n) {
//cerr << inputSeq[idx] << ", should be " << g << "\n";
br.emplace_back(inputSeq[idx] - n, g);
}
g = (g + 1) % n;
}
sort(all(br));
int l = 0;
for (auto b : br) {
replacementSeq[l++] = b.second + 1;
while (l <= b.first) {
replacementSeq[l] = n + l;
l++;
}
}
return l;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
