#include<gondola.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
int valid(int n, int inputSeq[])
{
vector<int>check(n+1),copy(n);
for(int i=0;i<n;i++)
{
copy[i]=inputSeq[i];
if(inputSeq[i]<=n)check[inputSeq[i]]=i+1;
}
sort(copy.begin(),copy.end());
for(int i=0;i<n;i++)if(copy[i]==copy[i+1])return 0;
int c=0,ans=1,pos,t;
for(int i=1;i<=n;i++)
{
if(check[i])
{
if(!c)c=i,pos=check[i];
else
{
t=check[i]-pos;
if(t<=0)t+=n;
if(t!=i-c)ans=0;
}
}
}
return ans;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<int>check(n+1),top(n),ans;
int c=0,pos;
for(int i=0;i<n;i++)
{
if(gondolaSeq[i]<=n)
{
c=gondolaSeq[i];
pos=i;
}
}
int left=0;
if(c)
{
left=pos-(c-1);
}
vector<pair<int,int>>newG;
for(int i=0;i<n;i++)
{
top[i]=i+1;
newG.push_back({gondolaSeq[i],(i+n-left)%n});
}
sort(newG.begin(),newG.end());
int t=n+1;
for(auto &k:newG)
{
if(top[k.second]==k.first)continue;
ans.push_back(top[k.second]);
top[k.second]=t;
t++;
while(top[k.second]!=k.first)
{
ans.push_back(top[k.second]);
top[k.second]++;
t++;
}
}
int sz=(int)ans.size();
for(int i=0;i<sz;i++)replacementSeq[i]=ans[i];
return sz;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq))return 0;
return 1;
}
