#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
int valid(int n, int inputSeq[]) {
for (int i = 0; i < n; i++) {
inputSeq[i]--;
}
pair<int, int> smallest = {1e9, -1};
for (int i = 0; i < n; i++) {
if (inputSeq[i] < smallest.first) {
smallest = {inputSeq[i], i};
}
}
set<int> seen;
if (smallest.first >= n) smallest.first = 0;
int next = smallest.first;
for (int i = smallest.second; i < n + smallest.second; i++) {
if (inputSeq[i % n] != next && (seen.count(inputSeq[i % n]) || inputSeq[i % n] < n)) {
return 0;
}
next = (next + 1) % n;
seen.insert(inputSeq[i % n]);
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<int> positions(n);
int temp = -1;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] <= n) {
temp = i;
}
}
if (temp == -1) {
for (int i = 0; i < n; i++) {
positions[i] = i + 1;
}
}
else {
int cur = gondolaSeq[temp];
for (int i = temp; i < n; i++) {
positions[i] = cur;
cur++;
if (cur > n) cur = 1;
}
for (int i = 0; i < temp; i++) {
positions[i] = cur;
cur++;
if (cur > n) cur = 1;
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i = 0; i < n; i++) {
pq.push({gondolaSeq[i], i});
}
int iRep = 0;
int cur = n + 1;
while (!pq.empty()) {
if (pq.top().first != positions[pq.top().second]){
replacementSeq[iRep] = positions[pq.top().second];
iRep++;
}
while (cur < gondolaSeq[pq.top().second]) {
replacementSeq[iRep] = cur;
iRep++;
cur++;
}
pq.pop();
}
return iRep;
}
int countReplacement(int n, int inputSeq[])
{return 0;}
