#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
int valid(int n, int t[])
{
rotate(t, min_element(t, t+n), t+n);
map<int, int> num;
int last = -n-1;
bool jo = true;
for(int i = 0; i < n; i++){
last++;
num[t[i]]++;
if(t[i] <= n){
if(last < 0)
last = t[i];
else if(t[i] != last)
jo = false;
}
}
for(auto p : num)
if(p.second > 1)
return 0;
return (int)jo;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
for(int i = 0; i < n; i++){
if(gondolaSeq[i] <= n){
int x = i-gondolaSeq[i]+1;
if(x < 0) x += n;
rotate(gondolaSeq, gondolaSeq + x, gondolaSeq + n);
break;
}
}
vector<pair<int, int>> v;
for(int i = 0; i < n; i++)
if(gondolaSeq[i] > n)
v.emplace_back(gondolaSeq[i], i+1);
sort(v.begin(), v.end());
int ret = 0, x = n;
for(auto p : v){
while(x < p.first){
replacementSeq[ret++] = p.second;
x++;
}
}
return ret;
}
//----------------------
const long long mod = (long long)1e9+9;
long long hatvany(long long n, long long h){
return (h ? hatvany(n*n%mod, h>>1)*(h&1ll ? n : 1ll)%mod : 1ll);
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq))
return 0;
bool fix = false;
vector<int> v;
for(int i = 0; i < n; i++){
if(inputSeq[i] <= n)
fix = true;
else
v.push_back(inputSeq[i]);
}
if(v.empty())
return 1;
sort(v.begin(), v.end());
long long meg = 1, last = n, db = (long long)v.size();
for(long long x : v){
meg = (meg * hatvany(db, x-last-1ll))%mod;
last = x;
}
return meg * (!fix ? (long long)n : 1ll) % mod;
}
