#include "gondola.h"
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll modu = ll(1e9) + 9ll;
int mod(int x, int n){
return ((x % n) + n) % n;
}
ll mod(ll x){
return (x % modu);
}
ll fast(ll base, ll power){
ll ret = 1ll;
while(power){
if(power & 1ll){
ret = mod(ret * base);
}
power >>= 1;
base = mod(base * base);
}
return ret;
}
int valid(int n, int inputSeq[])
{
int mn = n + 1;
int id = -1;
map<int, int> freq;
for(int i = 0; i < n; i++){
if(inputSeq[i] <= n and inputSeq[i] < mn){
mn = inputSeq[i];
id = i;
}
freq[inputSeq[i]]++;
if(freq[inputSeq[i]] > 1){
return 0;
}
}
if(id == -1){
return 1;
}
for(int i = 0; i < n; i++){
if(inputSeq[(i + id) % n] <= n and inputSeq[(i + id) % n] != mn){
return 0;
}
mn++;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int mn = n + 1;
int id = -1;
int not_used = n + 1;
int l = 0;
vector<pair<int, int>> v;
for(int i = 0; i < n;i++){
if(gondolaSeq[i] <= n and gondolaSeq[i] < mn){
mn = gondolaSeq[i];
id = i;
}
else if(gondolaSeq[i] > n){
v.push_back(make_pair(gondolaSeq[i], i));
}
}
sort(v.begin(), v.end());
if(id == -1){
id = 0;
}
else{
id = mod(id - mn + 1, n);
}
for(int i = 0; i < int(v.size()); i++){
replacementSeq[l] = mod(v[i].second - id, n) + 1;
l++;
while(not_used < v[i].first){
replacementSeq[l] = not_used;
not_used++;
l++;
}
not_used++;
}
return l;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
int mn = n + 1;
int id = -1;
map<int, int> freq;
for(int i = 0; i < n; i++){
if(inputSeq[i] <= n and inputSeq[i] < mn){
mn = inputSeq[i];
id = i;
}
freq[inputSeq[i]]++;
if(freq[inputSeq[i]] > 1){
return 0;
}
}
for(int i = 0; i < n and id != -1; i++){
if(inputSeq[(i + id) % n] <= n and inputSeq[(i + id) % n] != mn){
return 0;
}
mn++;
if(mn > n){
mn = 1;
}
}
//============================================================
ll ans = 1ll;
bool check = true;
ll not_used = ll(n) + 1ll;
vector<ll> v;
for(int i = 0; i < n;i++){
if(inputSeq[i] <= n){
check = false;
}
else{
v.push_back(ll(inputSeq[i]));
}
}
sort(v.begin(), v.end());
if(check){
ans = mod(ans * ll(n));
}
ll sz = ll(v.size());
for(ll i = 0ll; i < sz; i++){
ans = mod(ans * fast(sz - i, v[i] - not_used) );
not_used = v[i] + 1ll;
}
return int(ans);
}
