#include "gondola.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
int valid(int n, int inputSeq[])
{
bool flg = 0;
int off;
set<int> s;
Loop (i,0,n) {
if (s.count(inputSeq[i]))
return 0;
s.insert(inputSeq[i]);
if (inputSeq[i] <= n) {
if (flg && (inputSeq[i]-1 - i + n) % n != off)
return 0;
if (!flg) {
flg = 1;
off = (inputSeq[i]-1 - i + n) % n;
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int off = 0;
Loop (i,0,n)
if (gondolaSeq[i] <= n)
off = (gondolaSeq[i]-1 - i + n) % n;
vector<pii> a;
Loop (i,0,n)
a.push_back({gondolaSeq[i]-1, i});
sort(a.begin(), a.end());
int ans = 0;
int nxt = n;
Loop (i,0,n) {
if (a[i].first < n)
continue;
int lst = (a[i].second + off) % n;
while (nxt <= a[i].first) {
replacementSeq[ans++] = lst+1;
lst = nxt;
nxt++;
}
}
return ans;
}
//----------------------
const int mod = 1e9 + 9;
ll mpow(ll x, ll y) {ll ans=1;while(y){ans=y&1?ans*x%mod:ans;x=x*x%mod;y>>=1;}return ans;}
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq))
return 0;
int off = 0;
Loop (i,0,n)
if (inputSeq[i] <= n)
off = (inputSeq[i]-1 - i + n) % n;
vector<pii> a;
Loop (i,0,n)
a.push_back({inputSeq[i]-1, i});
sort(a.begin(), a.end());
ll ans = 1;
int nxt = n;
int cnt = n;
Loop (i,0,n) {
--cnt;
if (a[i].first < n)
continue;
ans = ans * mpow(cnt + 1, a[i].first - nxt) % mod;
nxt = a[i].first + 1;
}
if (a[0].first >= n)
ans = ans*n % mod;
return ans;
}
