#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
int valid(int n, int inputSeq[]) {
bool b = 1;
ll cnt = 0;
vll inp;
vll vis(250001);
vll bigger;
loop(i,0,n) {
vis[inputSeq[i]]++;
if (inputSeq[i] <=n) inp.push_back(inputSeq[i]);
else bigger.push_back(inputSeq[i]);
}
ll sz = bigger.size();
vll vis1(250002);
for (auto it :bigger) vis1[it]++;
loop(i,n+1,n+sz+1)
if (vis1[i]!=1) b= false;
loop(i,0,n) {
int it = inputSeq[i];
if (vis[it]>1) b= false;
}
loop(i,1,inp.size()) {
if (inp[i] < inp[i-1] && cnt!= 0 ) b = false;
if (inp[i] < inp[i-1]) cnt++;
if (inp[i] < inp[i-1] && (inp[i]!= 1 || inp[i-1]!= n) ) b= false;
}
return (b==1 ? 1: 0);
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
vb vis(250001);
loop(i,0,n) vis[gondolaSeq[i]] = 1;
ll j = 0, cnt =0 ;
loop(i,1,n) {
if (!vis[i]) {
replacementSeq[j] =i;
cnt++;
j++;
}
}
return cnt;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
