#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
int ind=0,val=1;
for(int i=0;i<n;i++)
{
if(inputSeq[i]<=n)
{
ind=i;
val=inputSeq[i];
}
}
val+=n;
for(int i=ind-1;i>=0;i--)
{
if(inputSeq[i]<=n)
{
int k=(val-(ind-i))%n;
if(k==0) k=n;
if(inputSeq[i]!=k)
{
return 0;
}
}
}
for(int i=ind+1;i<n;i++)
{
if(inputSeq[i]<=n)
{
int k=(val-(ind-i))%n;
if(k==0) k=n;
if(inputSeq[i]!=k)
{
return 0;
}
}
}
sort(inputSeq,inputSeq+n);
for(int i=1;i<n;i++)
{
if(inputSeq[i]==inputSeq[i-1])
{
return 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int ind=0,val=1;
vector<pair<int,int>> S;
for(int i=0;i<n;i++)
{
if(gondolaSeq[i]<=n)
{
ind=i;
val=gondolaSeq[i];
}
}
val+=n;
for(int i=ind;i>=0;i--)
{
if(gondolaSeq[i]>n)
{
int k=(val-(ind-i))%n;
if(k==0) k=n;
S.push_back({gondolaSeq[i],k});
}
}
for(int i=ind+1;i<n;i++)
{
if(gondolaSeq[i]>n)
{
int k=(val+(i-ind))%n;
if(k==0) k=n;
S.push_back({gondolaSeq[i],k});
}
}
if(S.size()==0) return 0;
sort(S.begin(),S.end());
int in=0,e=S[S.size()-1].first;
int l=0;
replacementSeq[l]=S[in].second;
l++;
for(int i=n+1;i<e;i++)
{
if(i==S[in].first)
{
in++;
replacementSeq[l]=S[in].second;
l++;
}
else
{
replacementSeq[l]=i;
l++;
}
}
return l;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
int MOD=1e9+9;
if(!valid(n,inputSeq)) return 0;
long long ans=1;
bool cz=1;
int ind=0,val=1;
vector<pair<int,int>> S;
for(int i=0;i<n;i++)
{
if(inputSeq[i]<=n)
{
ind=i;
val=inputSeq[i];
cz=0;
}
}
val+=n;
for(int i=ind;i>=0;i--)
{
if(inputSeq[i]>n)
{
int k=(val-(ind-i))%n;
if(k==0) k=n;
S.push_back({inputSeq[i],k});
}
}
for(int i=ind+1;i<n;i++)
{
if(inputSeq[i]>n)
{
int k=(val+(i-ind))%n;
if(k==0) k=n;
S.push_back({inputSeq[i],k});
}
}
if(S.size()==0) return 1;
sort(S.begin(),S.end());
int in=0,e=S[S.size()-1].first;
for(int i=n+1;i<e;i++)
{
if(i==S[in].first)
{
in++;
}
else
{
ans*=(S.size()-in);
ans%=MOD;
}
}
if(cz)
{
ans*=n;
ans%=MOD;
}
return ans;
}
