#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n,int inputSeq[]){
int offset=-1;
set<int> s;
for(int i=0;i<n;++i){
if(s.find(inputSeq[i])!=s.end())return 0;
s.insert(inputSeq[i]);
if(inputSeq[i]<=n){
if(offset==-1)offset=(inputSeq[i]-i+n)%n;
else if(offset!=(inputSeq[i]-i+n)%n)return 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
set<int> changed;
map<int,int> pos;
int offset=-1,dummy=0,cur=0;
int mx=0;
for(int i=0;i<n;++i){
if(gondolaSeq[i]<=n)offset=(gondolaSeq[i]-i+n)%n;
else{
changed.insert(gondolaSeq[i]);
dummy=i;
}
mx=max(mx,gondolaSeq[i]);
}
for(int i=0;i<n;++i){
if(gondolaSeq[i]>n){
pos[gondolaSeq[i]]=(i+offset<=n)?i+offset:(i+offset)%n;
}
}
cur=(dummy+offset<=n)?dummy+offset:(dummy+offset)%n;
int ori=cur;
for(int i=n+1;i<=mx;++i){
if(changed.find(i)==changed.end()||pos[i]==ori){
replacementSeq[i-n-1]=cur;
cur=i;
}
else{
replacementSeq[i-n-1]=pos[i];
}
}
return mx-n;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
