#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[]){
vector <pair<int,int>> s;
map <int,int> m;
for (int i = 0; i < n; i++) {
m[inputSeq[i]]++;
if (m[inputSeq[i]] == 2) {return 0;}
if (inputSeq[i] <= n) {
s.push_back({inputSeq[i],i+1});
}
}
int cnt = 0;
for (int i = 1; i < (s).size(); i++) {
if (s[i].first < s[i-1].first) {
cnt++;
if (s[i].first - s[i].second != (s[i-1].first - s[i-1].second)-n) {return 0;}
} else {
if (s[i].first - s[i].second != s[i-1].first - s[i-1].second) {return 0;}
}
}
// cout << cnt << endl;
return (cnt <= 1);
}
int replacement(int n, int a[], int ans[])
{
int c[n];
iota(c,c+n,1);
int cur = -1;
map <int,int> m;
int mx = -1;
for (int i = 0; i < n; i++) {
if (a[i] <= n) cur = i;
m[a[i]]=i;
mx = max(mx,a[i]);
}
if (cur != -1) {
int pos = a[cur];
for (int i = cur; i < n; i++) {
c[i] = pos++;
}
for (int i = 0; i < cur; i++) {
c[i] = pos++;
}
}
for (int i= n+1; i <= mx; i++) {
if (m[i]) {
ans[i-n-1] = c[m[i]];
c[m[i]-1] = i;
} else {
ans[i-n-1] = c[m[mx]];
c[m[mx]] = i;
}
}
return mx-n;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return 1;
}
