#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){
if (a[i - 1] == n){
v.push_back({1, a[i]});
a[i] = 1;
}
else{
v.push_back({a[i - 1] + 1, a[i]});
a[i] = a[i - 1] + 1;
}
}
}
for (int i = 0; i < st; ++i){
if (a[i] > n){
if (a[(i - 1) % n] == n){
v.push_back({1, a[i]});
a[i] = 1;
}
else{
v.push_back({a[(i - 1) % n] + 1, a[i]});
a[i] = a[(i - 1) % n] + 1;
}
}
}
sort(v.begin(), v.end(), [](pair<int, int> x, pair<int, int> y){
return x.second < y.second;
});
for (auto [first, second] : v){
while (first != second){
replacementSeq[opt] = first;
opt++;
first = ++cur;
}
}
return opt;
}
int countReplacement(int n, int inputSeq[]){
return 0;
}
