#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "gondola.h"
int valid(int n, int inputSeq[]){
int ind = -1;
for(int i = 0; i < n; i++){
if(inputSeq[i] <= n) ind = i;
}
if(ind == -1){
bool ok = 1;
map<int, int> vis;
for(int i = 0; i < n; i++){
if(vis[inputSeq[i]]) ok = 0;
vis[inputSeq[i]] = 1;
}
return ok;
}
vector<int> alternate(n);
for(int i = ind; i < n; i++){
alternate[i] = inputSeq[ind] + (i - ind);
if(alternate[i] > n) alternate[i] -= n;
}
for(int i = 0; i < ind; i++){
alternate[i] = alternate[n-1] + i + 1;
if(alternate[i] > n) alternate[i] -= n;
}
bool ok = 1;
map<int, int> vis;
for(int i = 0; i < n; i++){
if(vis[inputSeq[i]]) ok = 0;
vis[inputSeq[i]] = 1;
if(inputSeq[i] > n || inputSeq[i] == alternate[i]) continue;
ok = 0;
}
return ok;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int l, mx = 0;
int ind = -1;
for(int i = 0; i < n; i++){
mx = max(mx, gondolaSeq[i]);
if(gondolaSeq[i] <= n) ind = i;
}
l = (mx - n);
vector<int> alternate(n);
if(ind == -1){
for(int i = 0; i < n; i++){
alternate[i] = i+1;
}
}
else{
for(int i = ind; i < n; i++){
alternate[i] = gondolaSeq[ind] + (i - ind);
if(alternate[i] > n) alternate[i] -= n;
}
for(int i = 0; i < ind; i++){
alternate[i] = alternate[n-1] + i + 1;
if(alternate[i] > n) alternate[i] -= n;
}
}
vector<pair<int, int> > rep;
for(int i = 0; i < n; i++){
if(gondolaSeq[i] <= n) continue;
rep.pb({gondolaSeq[i], i});
}
sort(rep.begin(), rep.end());
int now = n + 1;
ind = 0;
for(auto itr: rep){
while(itr.first >= now){
replacementSeq[ind++] = alternate[itr.second];
alternate[itr.second] = now;
now++;
}
}
return l;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
