#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<ll, ll>
#define nyan "(=^･ω･^=)"
#define read_input freopen("in.txt","r", stdin)
#define print_output freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 3e5+10;
int next(int p, int n) {
int ret = (p + 1) % n;
return (ret == 0)? n : ret;
}
int prev(int p, int n) {
if(p == 0) return n-1;
else return p-1;
}
int valid(int n, int inputSeq[])
{
int f = 1, prev = -1;
for(int i = 0; i < n; i++) {
if(inputSeq[i] >= 1 && inputSeq[i] <= n) {
if(prev == -1) prev = inputSeq[i];
else if(next(prev, n) == inputSeq[i]) prev = inputSeq[i];
else f = 0;
}
}
set<int> s;
for(int i = 0; i < n; i++) s.insert(inputSeq[i]);
if(s.size() != n) return 0;
return f;
}
//----------------------
int pos[maxn];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
memset(pos, -1, sizeof pos);
vector<int> v, dummy, target(n);
int mx = 0, none = 1;
for(int i = 0; i < n; i++) {
if(gondolaSeq[i] > n) {
dummy.pb(i);
pos[gondolaSeq[i]] = i;
mx = max(mx, gondolaSeq[i]);
}
else none = 0;
}
for(int i = 0; i < n; i++) target[i] = gondolaSeq[i];
if(!none) {
for(int i = 0; i < n; i++) {
if(gondolaSeq[prev(i, n)] >= 1 && gondolaSeq[prev(i, n)] <= n)
gondolaSeq[i] = next(gondolaSeq[prev(i, n)], n);
}
for(int i = 0; i < n; i++) {
if(gondolaSeq[prev(i, n)] >= 1 && gondolaSeq[prev(i, n)] <= n)
gondolaSeq[i] = next(gondolaSeq[prev(i, n)], n);
}
}
else {
for(int i = 0; i < n; i++) gondolaSeq[i] = i+1;
}
for(int i = n+1, d = 0; i <= mx; i++) {
if(pos[i] == -1) {
while(gondolaSeq[dummy[d]] == target[dummy[d]]) d++;
v.pb(gondolaSeq[dummy[d]]), gondolaSeq[dummy[d]] = i;
}
else v.pb(gondolaSeq[pos[i]]), gondolaSeq[pos[i]] = i;
}
int idx = 0;
for(auto i : v) replacementSeq[idx++] = i;
return v.size();
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
