#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl
#define v first
#define pos second
vector<pair<lli, lli>> arr;
lli val,ult,a,res;
int valid(int n, int inputSeq[])
{
unordered_map<lli,lli> mapa;
lli ult = -1;
lli val = -1;
bool res,iguales = false;
rep(i,0,n-1) {
if (inputSeq[i] <= n) {
ult = i;
val = inputSeq[i];
}
if (mapa[inputSeq[i]] == 1) {iguales = true; break;}
else mapa[inputSeq[i]] = 1;
}
if (iguales) return 0;
if (ult == -1) return 1;
val -= ult;
if(val < 1) val += n;
res = true;
rep(i,0,n-1) {
if (inputSeq[i] <= n){
if (inputSeq[i] != val) {res = false; break;}
}
val++;
if (val > n) val = 1;
}
return res;
}
lli valEn (lli p, lli n) {
lli b = 0;
if (p < ult) {
b = val - (ult-p);
if (b < 0) b += n;
}
else {
b = val + (p-ult);
if (b > n) b -= n;
}
return b;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<pair<lli, lli>> arr;
val = -1;
ult = -1;
res = 0;
rep(i,0,n-1) {
if (gondolaSeq[i] <= n) {
ult = i;
val = gondolaSeq[i];
}
else arr.push_back({gondolaSeq[i],i});
a = gondolaSeq[i];
res = max(res,a);
}
sort(arr.begin(), arr.end());
lli pas = n;
lli cont = 0;
for (auto act : arr) {
a = valEn(act.pos,n);
rep(i,pas+1,act.v){
replacementSeq[cont] = a;
a = i;
cont++;
}
pas = act.v;
}
res -= n;
return res;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
