#include "gondola.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
int vis[1000001];
int res1[100001];
int valid(int n, int inputSeq[])
{
int ind = 0;
int num = 0;
for(int i = 0 ; i< n ; i++){
if(inputSeq[i]>=1 && inputSeq[i] <=n ){
ind = i;
num = inputSeq[i];
}
if(inputSeq[i] <1)
return 0;
if(vis[inputSeq[i]] ==1)
return 0;
vis[inputSeq[i]]=1;
}
if(num==0)
return 1;
for(int i = 0 ; i < n; i++)
if(inputSeq[i] <= n){
if( (ind + (inputSeq[i] - num) +n ) %n!=i )
return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int mx = 0;
int mxind=0;
int ind = 0;
int num = 0;
int cnt = 0;
for(int i = 0 ; i < n; i++){
vis[gondolaSeq[i]]=1;
if( gondolaSeq[i]>=1 && gondolaSeq[i] <=n ){
ind = i+1;
num = gondolaSeq[i];
}
if ( mx < gondolaSeq[i]){
mx = gondolaSeq[i];
mxind =i;
}
}
if(num > n){
replacementSeq[cnt]=1;
cnt ++;
for(int i =n+1;i<mx;i++ ){
if(vis[i]==0){
vis[i]=1;
replacementSeq[cnt]=i;
cnt ++;
}
}
for(int i = mxind+1; i<=n;i++){
replacementSeq[cnt]=i;
cnt ++;
}
for(int i = 1; i< mxind; i++){
replacementSeq[cnt]=i;
cnt ++;
}
return mx - n;
}
for(int i =1; i <=n ;i++){
res1[i-1] = (num + i -ind + n)%n ;
if(res1[i-1]==0)
res1[i-1]=n;
}
vector <int > vec;
for(int i = mx-1; i>n;i++){
if(vis[i]==0)
vec.push_back(i);
}
for(int i =0 ; i <n;i++)
if(gondolaSeq[i]!=res1[i]){
replacementSeq[cnt]=res1[i];
cnt ++;
while( vec.size () > 0 && gondolaSeq[i] > vec.back()){
replacementSeq[cnt]=vec.back();
cnt ++;
vec.pop_back();
}
}
return mx - n;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
int ind = 0;
int num = 0;
for(int i = 0 ; i< n ; i++){
if(inputSeq[i]>=1 && inputSeq[i] <=n ){
ind = i;
num = inputSeq[i];
}
if(inputSeq[i] <1)
return 0;
if(vis[inputSeq[i]] ==1)
return 0;
vis[inputSeq[i]]=1;
}
if(num!=0)
for(int i = 0 ; i < n; i++)
if(inputSeq[i] <= n){
if( (ind + (inputSeq[i] - num) +n ) %n!=i )
return 0;
}
return 1;
}
