#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int marc[maxn], pos[maxn], onde[maxn], need[maxn];
int valid(int n, int v[])
{
int val, ini, maior=1;
for(int i=0;i<n;i++) maior=max(maior,v[i]);
for(int i=1;i<=maior;i++) marc[maior]=0;
for(int i=0;i<n;i++){
if(marc[v[i]]) return 0;
marc[v[i]]++;
if(v[i]<=n){
val=v[i];
ini=i;
break;
}
}
for(int i=ini+1;i<n;i++){
if(marc[v[i]]) return 0;
marc[v[i]]++;
val++; val%=(n+1);
if(!val) val++;
if(v[i]>n) continue;
if(val!=v[i]) return 0;
}
return 1;
}
int replacement(int n, int v[], int resp[])
{
int maior=1;
for(int i=0;i<n;i++) maior=max(maior,v[i]);
for(int i=1;i<=maior;i++) need[i]=pos[i]=marc[i]=0;
int val, ini=-1;
for(int i=0;i<n;i++){
if(v[i]<=n){
val=v[i];
ini=i;
break;
}
}
if(ini==-1){
for(int i=1;i<=n;i++){
pos[i-1]=i;
onde[i]=i-1;
}
}else{
int og=val;
for(int i=ini;i<n;i++){
pos[i]=val;
onde[val]=i;
val++; val%=(n+1);
if(!val) val++;
}
val=og;
for(int i=ini;i>=0;i--){
pos[i]=val;
onde[val]=i;
val--;
if(!val) val+=n;
}
}
for(int i=0;i<n;i++){
marc[v[i]]++;
need[v[i]]=i;
}
int id=0;
set<pair<int,int>>tira; // cara e onde ele tá
for(int i=1;i<=n;i++) if(!marc[i]) tira.insert({i,onde[i]});
for(int i=n+1;i<=maior;i++){
if(!marc[i]){ // posso colocar em qlqr lugar
auto f=tira.begin();
resp[id]=f->first;
int lugar=f->second;
onde[i]=lugar;
pos[lugar]=i;
tira.erase(f);
id++;
tira.insert({i,onde[i]});
}else{ // tenho q colocar no lugar certo
int at=pos[need[i]];
tira.erase({at,onde[at]});
pos[need[i]]=i;
resp[id]=at;
id++;
}
}
return id;
}
int countReplacement(int n, int inputSeq[])
{
return -3;
}
