#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int cnt[maxn];
int valid(int n, int inputSeq[])
{
for (int i = 0; i < n; i ++)
{
int val = inputSeq[(i + 1) % n];
if (inputSeq[i] == n && val == 1)
continue;
if (val != inputSeq[i] + 1)
{
///cout << i << endl;
///cout << inputSeq[i] << " " << val << endl;
return 0;
}
}
return 1;
}
//----------------------
int order[maxn], to_go[maxn];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int pivot = 0;
while(pivot < n && gondolaSeq[pivot] > n)
pivot ++;
if (pivot == n)
pivot = 0;
order[gondolaSeq[pivot] - 1] = gondolaSeq[pivot];
for (int i = pivot + 1; i < n + pivot; i ++)
{
order[(gondolaSeq[pivot] - 1 + (i - pivot)) % n] = gondolaSeq[i % n];
}
///for (int i = 0; i < n; i ++)
/// cout << order[i] << " ";
///cout << endl;
int mx = 0, pt = 0;
for (int i = 0; i < n; i ++)
{
if (order[i] > n)
{
if (order[i] > mx)
{
mx = order[i];
pt = i + 1;
}
to_go[order[i]] = i + 1;
}
}
///cout << mx << " " << pt << endl;
int idx = 0, last_free = pt;
for (int i = n + 1; i <= mx; i ++)
{
if (to_go[i] != 0)
{
if (to_go[i] == pt)
replacementSeq[idx ++] = last_free;
else
replacementSeq[idx ++] = to_go[i];
}
else
{
replacementSeq[idx ++] = last_free;
last_free = i;
}
}
return max(0, mx - n);
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
