#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
int marc[MAXN], num[MAXN];
int id(int x, int n){
if(x == -1) return n - 1;
if(x == n) return 0;
return x;
}
int valid(int n, int inputSeq[]){
int pos_1 = -1;
for(int i=0; i<n; i++){
if(inputSeq[i] == 1) pos_1 = i;
marc[inputSeq[i]] = 0;
}
for(int i=0; i<n; i++){
marc[inputSeq[i]] ++;
if(marc[inputSeq[i]] > 1) return 0;
}
int cur_pos = id(pos_1 + 1, n);
while(cur_pos != pos_1){
if(inputSeq[cur_pos] <= n && inputSeq[id(cur_pos - 1, n)] <= n && inputSeq[cur_pos] != inputSeq[id(cur_pos - 1, n)] + 1) return 0;
cur_pos = id(cur_pos + 1, n);
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int pos = 1;
for(int i=0; i<n; i++){
if(gondolaSeq[i] <= n){
pos = min(pos, i);
}
}
num[pos] = gondolaSeq[pos];
int cur_num = gondolaSeq[pos] - 1;
int cur_pos = id(pos - 1, n);
while(cur_num > 0){
num[cur_pos] = cur_num;
cur_num --; cur_pos = id(cur_pos - 1, n);
}
cur_num = gondolaSeq[pos] + 1;
cur_pos = id(pos + 1, n);
while(cur_num <= n){
num[cur_pos] = cur_num;
cur_num ++; cur_pos = id(cur_pos + 1, n);
}
vector<pair<int, int>> v;
for(int i=0; i<n; i++){
if(gondolaSeq[i] > n){
v.push_back({gondolaSeq[i], num[i]});
}
}
sort(v.begin(), v.end());
int l = 0;
int cur = n + 1;
for(auto [x, i] : v){
replacementSeq[l ++] = i;
while(cur != x){
replacementSeq[l ++] = cur;
cur ++;
}
cur ++; // x nao quebra
}
// for(int i=0; i<l; i++) cout << replacementSeq[i] << " ";
// cout << "\n";
return -2;
}
int countReplacement(int n, int inputSeq[]){
return -3;
}
