#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
void rot(vector<int>& a) {
int n=a.size();
for (int i=0; i<n; ++i)
if (a[i]<=n) {
int st=(i-(a[i]-1)+n)%n;
rotate(a.begin(), a.begin()+st, a.end());
break;
}
}
int valid(int n, vector<int> a) {
if (*min_element(a.begin(), a.end())>n)
return 1;
vector<int> b=a;
sort(b.begin(), b.end());
for (int i=0; i+1<n; ++i)
if (b[i]==b[i+1])
return 0;
rot(a);
for (int i=0; i<n; ++i)
if (a[i]<=n&&a[i]!=i+1)
return 0;
return 1;
}
int valid(int n, int a[]) {
return valid(n, vector<int>(a, a+n));
}
int replacement(int n, vector<int> a, int b[]) {
assert(valid(n, a));
rot(a);
int mx=*max_element(a.begin(), a.end());
vector<int> who(mx+1, -1);
for (int i=0; i<n; ++i)
who[a[i]]=i;
vector<int> seq(n);
iota(seq.begin(), seq.end(), 1);
for (int i=n+1; i<=mx; ++i) {
int pos=who[i]!=-1?who[i]:who[mx];
b[i-n-1]=seq[pos];
seq[pos]=i;
}
return mx-n;
}
int replacement(int n, int a[], int b[]) {
return replacement(n, vector<int>(a, a+n), b);
}
const int M=1e9+9;
#define ll long long
ll bp(ll b, int p) {
ll r=1;
for (; p; p/=2, b=b*b%M)
if (p%2)
r=r*b%M;
return r;
}
int countReplacement(int n, vector<int> a) {
if (!valid(n, a))
return 0;
rot(a);
int free=0;
vector<int> pos;
for (int i : a) {
if (i>n) {
++free;
pos.push_back(i);
}
}
sort(pos.begin(), pos.end());
int last=n;
ll ans=1;
for (int i : pos) {
ans=ans*bp(free--, i-last-1)%M;
last=i;
}
if (*min_element(a.begin(), a.end())>n)
ans=ans*n%M;
return ans;
}
int countReplacement(int n, int a[]) {
return countReplacement(n, vector<int>(a, a+n));
}
