#include "gondola.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
int valid(int n, int inputSeq[])
{
int pos = -1;
for(int i = 0; i < n; i++){
if(inputSeq[i] == 1){
pos = i;
break;
}
}
bool seq = true;
int at = 1, lim = pos;
while(pos < n){
if(inputSeq[pos] == at){
pos++;
at++;
}
else{
seq = false;
break;
}
}
if(!seq) return 0;
pos = 0;
while(pos < lim){
if(inputSeq[pos] == at){
pos++;
at++;
}
else{
seq = false;
break;
}
}
if(!seq) return 0;
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int pos = -1;
for(int i = 0; i < n; i++){
if(gondolaSeq[i] >= 1 && gondolaSeq[i] <= n){
pos = i;
break;
}
}
if(pos == -1){
vi arr(n);
for(int i = 0; i < n; i++) arr[i] = gondolaSeq[i];
sort(arr.begin(), arr.end());
int at = 1, j = 0, rez =0;
for(int i = 0; i < n; i++){
while(at < arr[i]){
replacementSeq[j++] = at++;
rez++;
}
at++;
}
return rez;
}
else{
set<int> active;
map<int,int> replace;
for(int i = 0; i < n; i++) active.insert(gondolaSeq[i]);
int at = gondolaSeq[pos];
while(at <= n){
at++;
pos++;
pos%=n;
}
int j = 0, rez = 0, need = 1;
at=n+1;
for(int i = pos; i < n; i++){
replace[gondolaSeq[i]] = need++;
}
for(int i = 0; i < pos; i++)
replace[gondolaSeq[i]] = need++;
need=1;
set<int> out;
bool done[n+1];
memset(done, false, sizeof done);
for(int i = pos; i < n; i++){
//cout<<"At: "<<i<<" "<<need<<" "<<gondolaSeq[i]<<" "<<at<<endl;
if(gondolaSeq[i] == need){
need++;
continue;
}
else{
if(!done[need]){
replacementSeq[j++] = need;
done[need++] = true;
rez++;
}
while(at < gondolaSeq[i]){
if(active.find(at) != active.end()){
if(!done[replace[at]]){
done[replace[at]] = true;
replacementSeq[j++] = replace[at++];
rez++;
}
else
at++;
}
else{
replacementSeq[j++] = at++;
rez++;
}
}
}
}
for(int i = 0; i < pos; i++){
//cout<<"At: "<<i<<" "<<need<<" "<<gondolaSeq[i]<<" "<<at<<endl;
if(gondolaSeq[i] == need){
need++;
continue;
}
else{
if(!done[need]){
replacementSeq[j++] = need;
done[need++] = true;
rez++;
}
while(at < gondolaSeq[i]){
if(active.find(at) != active.end()){
if(!done[replace[at]]){
done[replace[at]] = true;
replacementSeq[j++] = replace[at++];
rez++;
}
else
at++;
}
else{
replacementSeq[j++] = at++;
rez++;
}
}
}
}
/*cout<<"NOT DONE: ";
for(int i = 1; i <= n; i++){
if(!done[i]){
cout<<i<<" ";
}
}
cout<<endl;
cout<<"END: "<<at<<" "<<replace[at]<<" "<<done[replace[at]]<<endl;
*/
if(replace[at] != 0 && !done[replace[at]]){
replacementSeq[j++] = replace[at];
rez++;
}
return rez;
}
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
