#include "gondola.h"
#include <stdio.h>
#include <string.h>
#define A 250000
#define MD 1000000009
int max(int a, int b) { return a > b ? a : b; }
int valid(int n, int aa[]) {
static char used[A + 1];
int i, j;
for (i = 0; i < n; i++) {
if (used[aa[i]])
return 0;
used[aa[i]] = 1;
}
for (i = 0; i < n; i++)
if (aa[i] <= n) {
for (j = 0; j < n; j++)
if (aa[(i + j) % n] <= n && aa[(i + j) % n] != (aa[i] - 1 + j) % n + 1)
return 0;
return 1;
}
return 1;
}
int replacement(int n, int aa[], int bb[]) {
static int ii[A + 1];
int i, a, a_, b, offset;
memset(ii, -1, (A + 1) * sizeof *ii);
offset = 0;
for (i = 0, a_ = -1; i < n; i++) {
ii[aa[i]] = i, a_ = max(a_, aa[i]);
if (aa[i] <= n)
offset = (aa[i] - 1 - i + n) % n;
}
for (a = n + 1, b = (ii[a_] + offset) % n + 1; a <= a_; a++)
if (a < a_ && ii[a] != -1)
bb[a - n - 1] = (ii[a] + offset) % n + 1;
else
bb[a - n - 1] = b, b = a;
return a_ - n;
}
int countReplacement(int n, int aa[]) {
static char used[A + 1];
int i, a, a_, k, ans, fixed;
if (!valid(n, aa))
return 0;
a_ = 0, fixed = 0;
for (i = 0; i < n; i++) {
used[aa[i]] = 1, a_ = max(a_, aa[i]);
if (aa[i] <= n)
fixed = 1;
}
k = 0, ans = 1;
for (a = a_; a > n; a--)
if (used[a])
k++;
else
ans = (long long) ans * k % MD;
if (!fixed)
ans = (long long) ans * n % MD;
return ans;
}
