#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 9;
const ll mxN = 1e6 + 5;
using namespace std;
int realS[mxN];
int valid(int n, int inputSeq[])
{
vector<bool> vis(250000 + 3);
int st = 0;
int val = 1;
for (int i = 0; i < n; i++)
{
if (vis[inputSeq[i]])
return 0;
vis[inputSeq[i]] = 1;
if (inputSeq[i] <= n)
{
st = i;
val = inputSeq[i];
}
}
int og = st;
while (1)
{
st++;
val++;
if (st >= n)
st = 0;
if (val > n)
val = 1;
if (st == og)
break;
if (inputSeq[st] != val && inputSeq[st] <= n)
return 0;
realS[inputSeq[st]] = val;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
set<int> s;
int mx = 0;
valid(n, gondolaSeq);
for (int i = 0; i < n; i++)
mx = max(mx, gondolaSeq[i]);
for (int i = 1; i <= mx; i++)
s.insert(i);
for (int i = 0; i < n; i++)
s.erase(gondolaSeq[i]);
int id = 0;
for (int i = n + 1; i <= mx; i++)
{
if (realS[i] == i)
continue;
// cout<<i<<' '<<realS[i]<<'\n';
if (!realS[i])
{
replacementSeq[id] = realS[mx];
realS[mx] = i;
}
else
replacementSeq[id] = realS[i];
id++;
}
return id;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
