#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int valid(int n, int inputSeq[])
{
for(int i=1;i<n;i++){
if(inputSeq[i] - inputSeq[i-1] != 1 && (inputSeq[i-1] != n || inputSeq[i] != 1))return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector <pi> stuf;
int rot = 0;
for(int i=0;i<n;i++){
if(gondolaSeq[i] <= n)rot = gondolaSeq[i] - i - 1;
}
if(rot < 0)rot += n;
for(int i=0;i<n;i++){
if(gondolaSeq[i] > n){
int tmp = i + rot + 1;
if(tmp > n)tmp -= n;
stuf.push_back({gondolaSeq[i], tmp});
}
}
sort(stuf.begin(), stuf.end());
int prv = n;
int in = 0;
for(auto [i, j] : stuf){
replacementSeq[in++] = j;
prv++;
for(int x = prv + 1; x <= i; x++)replacementSeq[in++] = x - 1;
prv = i;
}
return in;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
