#include "gondola.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
///Permutations
///Binary Exponentiation
///Determine whether a sequence is a gondola sequence, a possible replacement sequence and the number of replacement sequences
map<int,int> used;
int valid(int n, int inputSeq[])
{
int corresponding=1;
int id_less_n=0;
for(int i=0;i<n;i++){
if(inputSeq[i]<=n){
id_less_n=i;
corresponding=inputSeq[i];
break;
}
}
for(int i=id_less_n;i<n+id_less_n;i++){
if(used[ inputSeq[i%n] ]) return 0;
used[ inputSeq[i%n] ]=1;
if(inputSeq[i%n]>n){
corresponding=(corresponding%n)+1;
continue;
}
if(inputSeq[i%n]!=corresponding){
return 0;
}
corresponding=(corresponding%n)+1;
}
return 1;
}
typedef pair<int,int> pii;
//First is equal to the actual gondola
//Second is equal to the original gondola
bool byActual(pii a,pii b)
{
return a.first<b.first;
}
vector<pii> broken;
int corresponding=1;
int id_less_n=0;
void getBrokenGondolas(int n,int gondolaSeq[]) ///Return a vector with broken gondolas in in increasing order
{
for(int i=0;i<n;i++){
if(gondolaSeq[i]<=n){
id_less_n=i;
corresponding=gondolaSeq[i];
break;
}
}
for(int i=id_less_n;i<n+id_less_n;i++){
if(gondolaSeq[i%n]>n) broken.push_back(pii(gondolaSeq[i%n],corresponding));
corresponding=(corresponding%n)+1;
}
sort(broken.begin(),broken.end(),byActual);
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
getBrokenGondolas(n,gondolaSeq);
int L=0;
int act=n+1;
for(pii x: broken){
replacementSeq[L++]=x.second; //We add the original
while(act<x.first){
replacementSeq[L++]=act++; //Adds the intermediate gondolas
}
act++; //We update act since it is equal to the number of replaced gondola
}
return L;
}
typedef long long int ll;
ll mod=1000000009;
ll exponentiation(ll x,ll e)
{
if(e==0) return (ll)1;
ll product=exponentiation(x,e/2);
product=(product*product)%mod;
if(e%2==1) product=(product*x)%mod;
return product;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq)) return 0;
ll total=1;
getBrokenGondolas(n,inputSeq);
ll act=n+1;
ll N=broken.size();
for(ll i=0;i<N-1;i++){
ll x=broken[i].first;
ll k=x-act; //This is the number of numbers that have N-i choices
total=(total*exponentiation((ll)(N-i),k))%mod; //So we compute permutation with repetitions, of choices ((N-i)^k)
act=x+1;
}
if(corresponding==1 && inputSeq[0]!=1) total=(total*n)%mod; //There are not original gondolas
//So we can do n rotations
return total;
}
