#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include "gondola.h"
using namespace std;
int valid(int n, int seq[]){
map<int,int> mp;
for (int i=0;i<n;i++){
if (mp.find(seq[i]) != mp.end())
return 0;
mp[seq[i]];
}
vector<int> vc(n + 1);
for (int i=0;i<=n;i++){
if (i == n)
return 1;
if (seq[i] <= n){
for (int j=i;j<i + n;j++)
vc[(j - i + seq[i] - 1) % n + 1] = seq[j % n];
break;
}
}
for (int i=1;i<=n;i++)
if (vc[i] <= n and vc[i] != i)
return 0;
return 1;
}
int replacement(int n, int seq[], int ans[]){
vector<int> vc(n + 1);
vector<pair<int,int>> vc2;
for (int i=0;i<=n;i++){
if (i == n){
for (int j=0;j<n;j++)
vc[j+1] = seq[j];
}
else if (seq[i] <= n){
for (int j=i;j<i + n;j++)
vc[(j - i + seq[i] - 1) % n + 1] = seq[j % n];
break;
}
}
for (int i=1;i<=n;i++){
if (vc[i] > n)
vc2.push_back({vc[i], i});
}
sort(begin(vc2), end(vc2));
int cur = n + 1, sz = 0;
for (auto [vl, id] : vc2){
// cout<<cur<<" "<<vl<<" "<<id<<endl;
while (cur < vl)
ans[sz++] = id, id = cur++;
ans[sz++] = id;
cur++;
}
return sz;
}
int countReplacement(int n, int seq[]){
return 0;
}
