#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int MOD = 1000000009;
long long multiply(long long a, long long b)
{
long long ans = ((a % MOD) * (b%MOD)) % MOD;
return ans;
}
long long exponentiate(long long a, long long b)
{
long long ans = a;
for (int i = 0; i < (b-1); i++)
{
ans = multiply(ans,a);
}
return ans;
}
int valid(int n, int inputSeq[])
{
unordered_set<int> used;
int current = -1;
for (int i = 0; i < n; i++)
{
if (current==-1 && inputSeq[i] <= n)
{
current = inputSeq[i];
continue;
}
if (inputSeq[i] > n)
{
if (used.find(inputSeq[i])!=used.end())
{
return 0;
}
used.insert(inputSeq[i]);
if (current!=-1){current++;}
}
if (inputSeq[i] <= n)
{
if (current==n && inputSeq[i] != 1)
{
return 0;
}
if (current!=n&&inputSeq[i] != current+1)
{
return 0;
}
current = inputSeq[i];
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int l =0;
priority_queue<pair<int, int>,vector<pair<int,int>>, greater<pair<int,int>>> r;
vector<int> original(n,-1);
for (int i = 0; i < n; i++)
{
if (gondolaSeq[i] <= n)
{
int c = gondolaSeq[i];
for (int x = i; x < n; x++)
{
original[x] = c;
if (c == n)
{
c = 1;
}
else {
c++;
}
}
c = gondolaSeq[i];
for (int x = (i-1); x >= 0; x--)
{
original[x]=c-1;
if (c==1)
{
c = 5;
}
else{
c--;
}
}
break;
}
if (i==(n-1)&&original[0]==-1)
{
for (int i = 0; i < n; i++)
{
original[i]=i+1;
}
}
}
for (int i = 0; i < n; i++)
{
if (gondolaSeq[i] > n)
{
r.push({gondolaSeq[i],original[i]});
}
}
int next = n+1;
int arr_index = 0;
while (!r.empty())
{
int b = r.top().first;
int o = r.top().second;
r.pop();
replacementSeq[arr_index]=o;
l++;
next++;
arr_index++;
while (b>=next)
{
replacementSeq[arr_index] = next-1;
l++;
next++;
arr_index++;
}
}
return l;
}
int countReplacement(int n, int inputSeq[])
{
if (valid(n,inputSeq)==0)
{
return 0;
}
long long p = 1;
int next = n+1;
vector<int> replaced;
for (int i = 0; i < n; i++)
{
if (inputSeq[i] > n)
{
replaced.push_back(inputSeq[i]);
}
}
sort(replaced.begin(),replaced.end());
if (replaced.size()==n)
{
p = multiply(p,n);
}
if (!replaced.empty()){
for (int i = 0; i < replaced.size()-1; i++)
{
if (next != replaced[i])
{
long long num_options = replaced.size()-i;
long long gap = replaced[i]-next;
p = multiply(p,(exponentiate(num_options,gap)));
}
next = replaced[i]+1;
}}
return p;
}
/*int main()
{
cout << exponentiate(2,64) << endl;
cout << multiply(6,7) << endl;
}*/
