/**
* Method: Naively generates all permutations and counts them.
*
* Author: Catalin Francu
*
* Restrictions: values must be between 1 and 31.
*
* Implementation details:
*
* The bkt() function generates all permutations of the input set. To avoid
* duplicates, at every level it uses each value at most once. It keeps a bit
* mask to remember the values already used (hence the above restriction).
*
* As it progresses, bkt() keeps track of the legality of the permutation so
* far. It does so with the finite state automaton (STATES) documented below.
*
* processSolution() just increments a global counter, but you can compile
* with -DDEBUG to get a listing of all solutions.
*
* There is no need for modular arithmetic. It would take far too long to
* count 1.000.000.000 solutions.
**/
#include <stdio.h>
#define MAX_N 100
/* 0 if a < b, 1 if a == b, 2 if a > b */
#define CMP(a, b) (1 + (a > b) - (a < b))
/**
* states[s][c] = next state if the current state is s and
* CMP(previous number, current number) = c
**/
int STATES[6][3] =
{
{ 5, 0, 1 }, /* 0 = read a bunch of equal numbers, no inequality yet */
{ 2, 1, 1 }, /* 1 = read a smaller number; safe to move on to leg 2 */
{ 2, 2, 3 }, /* 2 = read a larger number; safe to move on to leg 3 */
{ 4, 3, 3 }, /* 3 = read a smaller number; safe to move on to leg 4 */
{ 4, 4, 5 }, /* 4 = read a larger number; safe to end; only final state */
{ 5, 5, 5 }, /* 5 = error state (absorbing) */
};
#define ACCEPTING_STATE 4
#define ERROR_STATE 5
int v[MAX_N + 1]; /* 1-based so we can test against v[0] without errors */
int n, numSolutions;
void processSolution() {
numSolutions++;
#ifdef DEBUG
for (int i = 1; i <= n; i++) {
printf("%d ", v[i]);
}
printf("\n");
#endif
}
void bkt(int level, int state) {
if (state == ERROR_STATE) {
return;
}
if (level > n) {
if (state == ACCEPTING_STATE) {
processSolution();
}
return;
}
unsigned seen = 0; /* bit mask of already used values */
for (int i = level; i <= n; i++) {
if (!(seen & (1 << v[i]))) {
int tmp = v[i];
v[i] = v[level];
v[level] = tmp;
seen |= (1 << v[level]);
int cmp = CMP(v[level - 1], v[level]);
int newState = (level == 1) ? 0 : STATES[state][cmp];
bkt(level + 1, newState);
tmp = v[i];
v[i] = v[level];
v[level] = tmp;
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &v[i]);
}
bkt(1, 0);
printf("%d\n", numSolutions);
}
