#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"
// int inputSeq[10000];
// int replacementSeq[10000];
// int gondolaSeq[10000];
int valid(int n, int inputSeq[]){
vector<pair<int,int>>v;
set<int>s;
for(int i=0; i<n; i++){
if(inputSeq[i]<=n)v.push_back({inputSeq[i],i});
if(s.find(inputSeq[i])!=s.end()){
return false;
}
s.insert(inputSeq[i]);
}
for(int i=1; i<v.size(); i++){
//if(v[i-1]==1)continue;
if(v[i].first==1){
continue;
}
if(v[i].first-v[i-1].first==v[i].second-v[i-1].second)continue;
return false;
}
//cout<<"NEKO"<<endl;
return true;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
// for(int i=0; i<n; i++){
// cout<<gondolaSeq[i]<<" ";
// }
if(valid(n,gondolaSeq)==false){
cout<<"NYAN"<<endl;
return 0;
}
else{
vector<int>v(n,0);
for(int i=0; i<n; i++){
if(gondolaSeq[i]<=n){
v[i]=gondolaSeq[i];
}
}
for(int i=0; i<n; i++){
if(v[i]!=0){
for(int j=i+1; j<n; j++){
v[j]=v[j-1]+1;
v[j]%=(n+1);
if(v[j]==0)v[j]++;
}
break;
}
}
// for(int i=0; i<n; i++){
// cout<<v[i]<<" ";
// }
for(int i=n-1; i>=0; i--){
if(v[i]!=0){
for(int j=i+1; j<n; j++){
if(v[j]==0){
v[j]=v[j]+n+1+v[j-1]-1;
v[j]%=(n+1);
}
}
}
}
// for(int i=0; i<n; i++){
// cout<<v[i]<<" ";
// }
vector<int>bati;
map<int,int>mp;
vector<pair<int,int>>ixvi;
for(int i=0; i<n; i++){
mp[gondolaSeq[i]]++;
if(gondolaSeq[i]>n){
ixvi.push_back({gondolaSeq[i]-1,n+1});
}
}
for(int i=1; i<=n; i++){
if(mp[i]==0)bati.push_back(i);
}
for(int i=0; i<ixvi.size(); i++){
for(int j=ixvi[i].second; j<=ixvi[i].first; j++){
bati.push_back(j);
}
}
int k=0;
for(auto a:bati){
cout<<a<<" ";
replacementSeq[k]=a;
k++;
}
return bati.size();
}
//return 0;
}
int countReplacement(int n, int inputSeq[]){
return 0;
}
