#include "gondola.h"
#include <set>
#include <vector>
#include <algorithm>
#include <cstdio>
int valid(int n, int inputSeq[])
{
int shift=-1;
std::set<int> used;
for(int i=0;i<n;i++){
if(used.count(inputSeq[i])) return 0;
used.insert(inputSeq[i]);
if(inputSeq[i]<=n){
int new_shift=(inputSeq[i]-i+n)%n;
if(shift!=-1&&shift!=new_shift) return 0;
shift=new_shift;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
for(int i=0;i<n;i++){
gondolaSeq[i]--;
}
int shift=0;
for(int i=0;i<n;i++){
if(gondolaSeq[i]<n){
shift=(gondolaSeq[i]-i+n)%n;
break;
}
}
std::vector<int> seq(n);
for(int i=0;i<n;i++){
seq[i]=(i+shift)%n;
}
/*
for(int i=0;i<n;i++){
printf("given: %d\n",gondolaSeq[i]);
}
for(int i=0;i<n;i++){
printf("seq: %d\n",seq[i]);
}
*/
auto max=std::max_element(gondolaSeq,gondolaSeq+n);
std::vector<int> where(*max+1,max-gondolaSeq);
for(int i=0;i<n;i++){
where[gondolaSeq[i]]=i;
}
for(int x=n;x<=*max;x++){
//printf("where[%d]=%d: %d\n",x,where[x],seq[where[x]]);
replacementSeq[x-n]=seq[where[x]];
seq[where[x]]=x;
}
int l=*max+1-n;
for(int i=0;i<l;i++){
replacementSeq[i]++;
}
return l;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
