#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
int valid(int n, int inputSeq[]) {
int fixed = -1;
vector<int> aux(MAX_N, 0);
for(int i = 0; i < n; ++i)
if(inputSeq[i] <= n)
fixed = i;
for(int i = 0; i < n; ++i)
aux[i] = inputSeq[i];
sort(aux.begin(), aux.begin() + n);
for(int i = 0; i < n - 1; ++i) // All gondolas must be distinct
if(aux[i] == aux[i + 1])
return false;
if(fixed == -1) // All gondolas have been replaced
return true;
for(int i = 0; i < n; ++i) {
int expected = (inputSeq[fixed] + i - 1) % n + 1;
int expectedPos = (fixed + i) % n;
if(!(inputSeq[expectedPos] == expected || inputSeq[expectedPos] > n))
return false;
}
return true;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int top = 0, lastVal = n;
int fixed = -1;
vector<pair<int, int> > aux;
for(int i = 0; i < n; ++i) {
if(gondolaSeq[i] > n)
aux.push_back(make_pair(gondolaSeq[i], i));
else
fixed = i;
}
sort(aux.begin(), aux.end());
for(auto it: aux) {
int expectedVal;
if(fixed > -1)
expectedVal = (gondolaSeq[fixed] + it.second - fixed + 2 * n - 1) % n + 1;
else
expectedVal = it.second;
replacementSeq[top++] = expectedVal;
++lastVal;
while(lastVal < it.first) {
replacementSeq[top++] = lastVal;
lastVal++;
}
}
return top;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
