#include "gondola.h"
#include<algorithm>
#include<iostream>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
const int MAXN=250010;
int arr[MAXN], pos[MAXN];
bool seen[MAXN];
int valid(int n, int inputSeq[])
{
forn(i, n){
if(seen[inputSeq[i]]) return 0;
seen[inputSeq[i]]=true;
}
auto itr=min_element(inputSeq, inputSeq+n);
if(*itr>=n) return 1;
auto tmp=itr, last=itr;
while(true){
if(*tmp<=n){
int d1=*tmp-*last, d2=tmp-last;
if(d2<0) d2+=n;
if(d1!=d2) return 0;
last=tmp;
}
tmp++;
if(tmp==inputSeq+n) tmp=inputSeq;
if(tmp==itr) break;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int offset=0;
forn(i, n) if(gondolaSeq[i]<=n) offset=i-gondolaSeq[i]+1;
if(offset<0) offset+=n;
int cur=offset, num=1;
while(true){
arr[cur++]=num++;
if(cur>=n) cur-=n;
if(cur==offset) break;
}
int mx=max_element(gondolaSeq, gondolaSeq+n)-gondolaSeq;
forn(i, gondolaSeq[mx] + 1) pos[i]=-1;
forn(i, n) pos[gondolaSeq[i]]=i;
int ans=0;
forsn(i, n+1, gondolaSeq[mx] + 1){
int p=pos[i];
if(p==-1) p=mx;
replacementSeq[ans++]=arr[p];
arr[p]=i;
}
return ans;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
