#include "gondola.h"
#include <bits/stdc++.h>
#define debug(x) std::cout << #x << " = " << x << '\n'
int valid(int n, int inputSeq[])
{
int firstPos = -1;
int correctNumber = 0;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n && firstPos == -1) {
firstPos = i;
correctNumber = inputSeq[i];
}
if (firstPos != -1) {
if (inputSeq[i] <= n && correctNumber != inputSeq[i]) {
return 0;
}
correctNumber = (correctNumber == n)? 1 : correctNumber + 1;
}
}
int bucket[250005];
memset(bucket, 0, sizeof(bucket));
for (int i = 0; i < n; i++) {
if (bucket[inputSeq[i]] == 1)
return 0;
bucket[inputSeq[i]] = 1;
}
return 1;
}
//----------------------
struct gondola {
int actual;
int original;
};
bool byActual(gondola a, gondola b) {
return a.actual < b.actual;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int len = 0;
int firstPos = -1;
int correctNumber = 0;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] <= n && firstPos == -1) {
firstPos = i;
correctNumber = gondolaSeq[i];
break;
}
}
if (firstPos == -1) {
firstPos = 0;
correctNumber = 1;
}
gondola gondolas[n + 3];
for (int i = firstPos; i < n; i++) {
gondolas[i].actual = gondolaSeq[i];
gondolas[i].original = correctNumber;
correctNumber = (correctNumber == n)? 1 : correctNumber + 1;
}
for (int i = 0; i < firstPos; i++) {
gondolas[i].actual = gondolaSeq[i];
gondolas[i].original = correctNumber;
correctNumber = (correctNumber == n)? 1 : correctNumber + 1;
}
std::sort(gondolas, gondolas + n, byActual);
int nextAvailable = n + 1;
for (int i = 0; i < n; i++) {
if (gondolas[i].actual <= n) continue;
replacementSeq[len++] = gondolas[i].original;
while (nextAvailable < gondolas[i].actual) {
replacementSeq[len++] = nextAvailable++;
}
nextAvailable = gondolas[i].actual + 1;
}
return len;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
