#include "gondola.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
int valid(int n, int inputSeq[])
{
bool flg = 0;
int off;
set<int> s;
Loop (i,0,n) {
if (s.count(inputSeq[i]))
return 0;
s.insert(inputSeq[i]);
if (inputSeq[i] <= n) {
if (flg && (inputSeq[i]-1 - i + n) % n != off)
return 0;
if (!flg) {
flg = 1;
off = (inputSeq[i]-1 - i + n) % n;
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int off = 0;
Loop (i,0,n)
if (gondolaSeq[i] <= n)
off = (gondolaSeq[i]-1 - i + n) % n;
vector<pii> a;
Loop (i,0,n)
a.push_back({gondolaSeq[i]-1, i});
sort(a.begin(), a.end());
int ans = 0;
int nxt = n;
Loop (i,0,n) {
if (a[i].first < n)
continue;
int lst = (a[i].second + off) % n;
while (nxt <= a[i].first) {
replacementSeq[ans++] = lst+1;
lst = nxt;
nxt++;
}
}
return ans;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
