#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
set<int> st;
for (int i=0; i<n; ++i) if (inputSeq[i]<=n && inputSeq[(i+1)%n]<=n){
if (inputSeq[i]%n+1!=inputSeq[(i+1)%n]){
return 0;
}
}
for (int i=0; i<n; ++i) if (!st.insert(inputSeq[i]).second) return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int max_id=max_element(gondolaSeq, gondolaSeq+n)-gondolaSeq;
int max_val=gondolaSeq[max_id];
vector<int> pos(3e5, -1);
vector<int> perm(n);
iota(perm.begin(), perm.end(), 1);
for (int i=0; i<n; ++i) pos[gondolaSeq[i]]=i;
for (int i=0; i<n; ++i) if (gondolaSeq[i]<=n){
perm[i]=gondolaSeq[i];
for (int j=(i+1)%n, k=perm[i]%n+1; j!=i; j=(j+1)%n, k=k%n+1) perm[j]=k;
break;
}
int cnt=0;
for (int i=n+1; i<=max_val; ++i){
if (pos[i]!=-1){
replacementSeq[cnt++]=perm[pos[i]];
perm[pos[i]]=i;
}else{
replacementSeq[cnt++]=perm[max_id];
perm[max_id]=i;
}
}
return cnt;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
