#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
bool exist[25000];
int valid(int n, int a[]){
memset(exist, false, sizeof(exist));
int app = -1;
for (int i = 0; i < n; ++i){
if (exist[a[i]]) return false;
exist[a[i]] = true;
if (a[i] <= n && app == -1) app = i;
}
if (app == -1) return 1;
for (int i = app + 1; i < n; ++i){
if (a[i] <= n){
if (a[i] == 1 && a[i - 1] != n) return 0;
if (a[i] != 1 && a[i - 1] + 1 != a[i]) return 0;
}
else a[i] = a[i - 1] + 1;
}
return 1;
}
int replacement(int n, int a[], int replacementSeq[]){
int opt = 0, cur = n, st = -1;
vector<pair<int, int>> v;
for (int i = 0; i < n; ++i){
if (a[i] <= n && st == -1) st = i;
}
if (st == -1){
st = 0;
v.push_back({1, a[0]});
a[0] = 1;
}
for (int i = st + 1; i < n; ++i){
if (a[i] > n){
v.push_back({a[(i - 1 + n) % n] % n + 1, a[i]});
a[i] = a[(i - 1 + n) % n] % n + 1;
}
}
for (int i = 0; i < st; ++i){
if (a[i] > n){
v.push_back({a[(i - 1 + n) % n] % n + 1, a[i]});
a[i] = a[(i - 1 + n) % n] % n + 1;
}
}
sort(v.begin(), v.end(), [](const pair<int, int>& x, const pair<int, int>& y){
return x.second < y.second;
});
for (int i = 0; i < v.size(); ++i){
int first = v[i].first, second = v[i].second;
while (first < second){
replacementSeq[opt] = first;
opt++;
first = ++cur;
}
}
return opt;
}
int countReplacement(int n, int inputSeq[]){
return 0;
}
