Ethan Finds the Maximum Element This is a problem that the Hacker Cup team made for the 2018 Facebook Hacker Cup, but we ended up not using it (though Ethan struggles through a variety of other challenges). Normally code size isn't a factor in the Hacker Cup, but we thought this would make for an interesting code golf challenge. We look forward to seeing how a different sort of competitive programmer tackles this problem!



Ethan Finds the Maximum Element

Ethan has been given quite the challenging programming assignment in school: given a list of \$N\ (1 &lt;= N &lt;= 50)\$ distinct integers \$A_{1..N}\ (1 &lt;= A_i &lt;= 100)\$, he must find the largest one!

Ethan has implemented an algorithm to solve this problem, described by the following pseudocode:


Set \$m\$ to be equal to \$A_1\$.
Iterate \$i\$ upwards from 2 to \$N\$ (inclusive), and for each \$i\$, if \$A_i &gt; A_{i-1}\$, set \$m\$ to be equal to \$A_i\$.
Output \$m\$.


Sometimes this algorithm will output the correct maximum value, but other times it sadly won't.

As Ethan's teaching assistant, you have some say in what input data his solution will be evaluated on. The professor has given you a list of \$N\$ distinct integers \$A_{1..N}\$ to work with, but you may shuffle them into any permutation you'd like before feeding them into Ethan's program. This is your opportunity to show some mercy!

For how many different permutations of \$A_{1..N}\$ would Ethan's algorithm produce the correct output?

Input Format:

Line 1: 1 integer, \$N\$
Line 2: \$N\$ space-separated integers, \$A_{1..N}\$

Output Format:

1 integer, the number of permutations of \$A\$ for which Ethan's algorithm would produce the correct output.

Sample Input 1:

1  
100


Sample Output 1:

1


Explanation:

Only one permutation of \$[100]\$ exists, and Ethan's program would correctly output 100 for it.

Sample Input 2:

3  
16 82 43


Sample Output 2:

5


Explanation:

Ethan's program would correctly output 82 for 5 of the 6 possible permutations of \$[16, 82, 43]\$. However, when \$A = [82, 16, 43]\$, it would incorrectly output 43 instead.

Sample Input 3:

10  
26 81 40 5 65 19 87 27 54 15


Sample Output 3:

986410


Rules

This is code-golf, so shortest answer (in bytes) wins!
APL (Dyalog Unicode), 5 3 bytes



⍳⊥×


Try it online!

Adám gave me an inspiration to golf this further.

How it works

⍳⊥×  Monadic train. Input: n, the length of array A.
  ×  v: Signum, which always gives 1 because n ≥ 1
⍳    B: An array of 0..n-1
 ⊥   Scalar-expand v to get V, a length-n vector of ones,
       then mixed base conversion of V in base B




APL (Dyalog Unicode), 5 bytes



⍳⊥⍴∘1


Try it online!

Edited to remove modulo 107

Uses HyperNeutrino's formula, but optimized through the use of ⊥ (mixed base conversion) directly. Uses ⎕IO←0.

How the code works

⍳⊥⍴∘1  Monadic train. Input: n, the length of array A.
  ⍴∘1  V: An array of 1's of length n
⍳      B: An array of 0..n-1
 ⊥     Mixed base conversion of V in base B


How the ⊥ works

base:  0         1         2         .. n-3         n-2 n-1
digit: 1         1         1         .. 1           1   1
value: 1×..(n-1) 2×..(n-1) 3×..(n-1) .. (n-2)×(n-1) n-1 1
sum of all digit values is the answer.