#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
int valid(int n, int inputSeq[])
{
int shift=-1;
int i;
for(i=0;i<n;++i)
if(inputSeq[i]<=n){
if(shift==-1)
shift=(i+1-inputSeq[i]+n)%n;
else
if((i+1-shift+n)%n!=inputSeq[i]%n)
return 0;
}
sort(inputSeq,inputSeq+n);
for(i=0;i<n-1;++i)
if(inputSeq[i]==inputSeq[i+1])
return 0;
return 1;
}
struct per{
int val,pos;
bool operator<(per ot){
return val>ot.val;
}
};
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int shift=-1;
int i;
for(i=0;i<n;++i)
if(gondolaSeq[i]<=n)
shift=(i+1-gondolaSeq[i]+n)%n;
if(shift==-1)
shift=0;
vector<per>v;
for(i=0;i<n;++i)
if(gondolaSeq[i]>n)
v.push_back({gondolaSeq[i],i});
int len=0;
if(!v.empty()){
sort(v.begin(),v.end());
int ult=(v[0].pos-shift+n)%n+1;
while(!v.empty()){
++len;
if(n+len==v.back().val){
replacementSeq[len-1]=((v.size()>1)?((v.back().pos-shift+n)%n+1):ult);
v.pop_back();
}
else{
replacementSeq[len-1]=ult;
ult=n+len;
}
}
}
return len;
}
int countReplacement(int n, int inputSeq[])
{
return -3;
}
