#include "gondola.h"
#include <assert.h>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
bool visited[250003];
struct dato{
int valor;
int pos;
};
bool operator <(const dato &a, const dato &b){
return a.valor < b.valor;
}
dato gon[250003];
int valid(int n, int inputSeq[])
{
int index = 0, aux, valor = 1;
for (int i = 0; i < n; i++){
aux = inputSeq[i];
if (aux <= n){
index = i;
valor = aux;
break;
}
}
for (int i = index; i < n + index; i++){
if (visited[ inputSeq[i % n] ]) return 0;
visited[ inputSeq[i % n] ] = true;
if (inputSeq[i % n] > n){
valor = (valor % n) + 1;
continue;
}
if (inputSeq[i % n] != valor) return 0;
valor = (valor % n) + 1;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int index = 0, aux, valor = 1, L = 0, g = n + 1;
for (int i = 0; i < n; i++){
aux = gondolaSeq[i];
if (aux <= n){
index = i;
valor = aux;
break;
}
}
int posi = 0;
for (int i = index; i < n + index; i++){
aux = gondolaSeq[i % n];
if (aux > n ){
gon[posi].valor = aux;
gon[posi].pos = valor;
posi++;
}
valor = (valor % n) + 1;
}
sort (gon + 0, gon + posi);
g = n + 1;
for (int i = 0; i < posi; i++){
if (gon[i].valor <= n) continue;
replacementSeq[L] = gon[i].pos;
L++;
while (g < gon[i].valor){
replacementSeq[L] = g;
g++;
L++;
}
g = gon[i].valor + 1;
}
return L;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
