#include "gondola.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
void rot(int n,int inputSeq[])
{
int gmn=0;
for(int i=0;i<n;i++)
{
if(inputSeq[i]<inputSeq[gmn])
gmn=i;
}
rotate(inputSeq,inputSeq+gmn,inputSeq+n);
return;
}
int valid(int n,int inputSeq[])
{
set<int> vis;
for(int i=0;i<n;i++)
{
if(vis.find(inputSeq[i])!=vis.end())
return 0;
vis.insert(inputSeq[i]);
}
rot(n,inputSeq);
for(int i=0;i<n;i++)
{
if(inputSeq[i]<=n && inputSeq[i]!=inputSeq[0]+i)
return 0;
}
return 1;
}
bool comp_se(pair<int,int> a,pair<int,int> b)
{
if(a.se==b.se)
return a.fi<b.fi;
return a.se<b.se;
}
int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
int l=0;
vector<pair<int,int>> ch;
rot(n,gondolaSeq);
for(int i=0;i<n;i++)
{
if(gondolaSeq[i]>n)
ch.emplace_back((gondolaSeq[0]+i-1)%n+1,gondolaSeq[i]);
}
sort(ch.begin(),ch.end(),comp_se);
int nxt=n+1;
for(auto v:ch)
{
replacementSeq[l++]=v.fi;
while(nxt<v.se)
replacementSeq[l++]=nxt++;
nxt++;
}
return l;
}
int countReplacement(int n,int inputSeq[])
{
return 0;
}
