#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 250100;
bool exist[maxn];
int fin_val[maxn];
int valid(int n, int arr[]) {
bool check = true;
for(int i=1;i<n;i++) {
if(arr[i] > n) continue;
else if(arr[i] == 1) {
if(arr[i-1] < n)
check = false;
}
else {
if(arr[i-1] <= n && arr[i-1] != arr[i] - 1) check = false;
}
}
sort(arr, arr+n);
for(int i=1;i<n;i++) {
if(arr[i] == arr[i-1]) check = false;
}
if(check) return 1;
else return 0;
}
//----------------------
int replacement(int n, int arr[], int replacementSeq[]) {
int maxm = 0;
int found_i = 0, st_val = 1;
for(int i=0;i<n;i++) {
exist[arr[i]] = true;
if(arr[i] <= n) {
found_i = i;
st_val = arr[i];
}
maxm = max(maxm, arr[i]);
}
exist[n] = true;
int l = maxm - n;
for(int i=found_i;i<n;i++) {
fin_val[i] = st_val;
st_val++;
if(st_val == n + 1) st_val = 1;
}
for(int i=0;i<found_i;i++) {
fin_val[i] = st_val;
st_val++;
if(st_val == n + 1) st_val = 1;
}
for(int i=0;i<n;i++) {
while(!exist[arr[i]-1] && arr[i] > n) {
replacementSeq[arr[i]-n-1] = arr[i] - 1;
arr[i]--;
}
if(arr[i] > n) replacementSeq[arr[i]-n-1] = fin_val[i];
}
return l;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
/*int main() {
int arr[] = {3, 1, 4};
int arr2[1];
cout<<replacement(3, arr, arr2);
}*/
