#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pii;
int valid(int n, int inputSeq[]){
vector<bool> marc(250'500, false);
int u = -1;
for(int i = 0; i < n; i++){
if(marc[inputSeq[i]]) return 0;
marc[inputSeq[i]] = true;
}
for(int i = 0; i < n; i++) if(inputSeq[i] <= n){
u = i;
break;
}
if(u == -1) return 1;
int dif = (inputSeq[u]-u+n)%n;
for(int i = 0; i < n; i++) if(inputSeq[i] <= n){
if((inputSeq[i]-i+n)%n != dif) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
vector<pii> mod; //
int dif = 0;
for(int i = 0; i < n; i++) if(gondolaSeq[i] <= n){
dif = (gondolaSeq[i]-i+n)%n;
break;
}
for(int i = 0; i < n; i++) if(gondolaSeq[i] > n){
int p = (i+dif+n)%n;
if(p == 0) p = n;
mod.emplace_back(gondolaSeq[i], p);
}
sort(mod.begin(), mod.end());
int nxt = n+1, rid = 0; //nxt = next gondola to be used
for(pii no : mod){
replacementSeq[rid++] = no.ss;
while(nxt < no.ff){
replacementSeq[rid++] = nxt;
nxt++;
}
}
return rid;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
