#include "gondola.h"
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int used[250005];
int valid(int n, int inputSeq[])
{
int corresponding=1;
int id_less_n=0;
for(int i=0;i<n;i++){
if(inputSeq[i]<=n){
id_less_n=i;
corresponding=inputSeq[i];
break;
}
}
for(int i=id_less_n;i<n+id_less_n;i++){
if(used[ inputSeq[i%n] ]) return 0;
used[ inputSeq[i%n] ]=1;
if(inputSeq[i%n]>n){
corresponding=(corresponding%n)+1;
continue;
}
if(inputSeq[i%n]!=corresponding){
return 0;
}
corresponding=(corresponding%n)+1;
}
return 1;
}
typedef pair<int,int> pii;
//First is equal to the actual gondola
//Second is equal to the original gondola
bool byActual(pii a,pii b)
{
return a.first<b.first;
}
vector<pii> broken;
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int corresponding=1;
int id_less_n=0;
for(int i=0;i<n;i++){
if(gondolaSeq[i]<=n){
id_less_n=i;
corresponding=gondolaSeq[i];
break;
}
}
for(int i=id_less_n;i<n+id_less_n;i++){
if(gondolaSeq[i%n]>n) broken.push_back(pii(gondolaSeq[i%n],corresponding));
corresponding=(corresponding%n)+1;
}
sort(broken.begin(),broken.end(),byActual);
int L=0;
int act=n+1;
for(pii x: broken){
replacementSeq[L++]=x.second; //We add the original
while(act<x.first){
replacementSeq[L++]=act++;
}
act++; //We update act since it is equal to the number of replaced gondola
}
return L;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return 1;
}
