[Question]
  [
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](https://www.facebook.com/hackercup/problem/1153996538071503/) [variety](https://www.facebook.com/hackercup/problem/232395994158286/) [of](https://www.facebook.com/hackercup/problem/988017871357549/) [other](https://www.facebook.com/hackercup/problem/467235440368329/) [challenges](https://www.facebook.com/hackercup/problem/278591946122939/)). 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 has been given quite the challenging programming assignment in school: given a list of \$N\ (1 \le N \le 50)\$ distinct integers \$A\_{1..N}\ (1 \le A\_i \le 100)\$, he must find the largest one!
Ethan has implemented an algorithm to solve this problem, described by the following pseudocode:
1. Set \$m\$ to be equal to \$A\_1\$.
2. Iterate \$i\$ upwards from 2 to \$N\$ (inclusive), and for each \$i\$, if \$A\_i > A\_{i-1}\$, set \$m\$ to be equal to \$A\_i\$.
3. 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](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so shortest answer (in bytes) wins!
  
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~5~~ 3 bytes
```
⍳⊥×
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkG/x/1bn7UtfTw9P9pQO6j3j6ITFfzofXGj9omAnnBQc5AMsTDM/h/2qEVxgqmCmYKhgZcj3rngpimCsZGZgqWFmYmhgYA "APL (Dyalog Unicode) – 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)](https://www.dyalog.com/), 5 bytes
```
⍳⊥⍴∘1
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkG/x/1bn7UtfRR75ZHHTMM/6cBxR719kGku5oPrTd@1DYRyAsOcgaSIR6ewf/TDq0wVjBVMFMwNOB61DsXxDRVMDYyU7C0MDMxNAAA "APL (Dyalog Unicode) – Try It Online")
*Edited to remove modulo 107*
Uses [HyperNeutrino's formula](https://codegolf.stackexchange.com/a/194804/78410), 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.
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 6 bytes
```
RU×\S:
```
[Try it online!](https://tio.run/##y0rNyan8/z8o9PD0mGCr////mwEA "Jelly – Try It Online")
Let's analyze under which scenarios this algorithm works.
If the maximum element is at the end of the list, this obviously works, since \$A\_N>A\_{N-1}\$ and it is processed last. This gives \$(N-1)!\$ possibilities.
If the maximum element is at the second last position, then this obviously works, since \$A\_N<A\_{N-1}\$ so it is not processed, and \$A\_{N-1}>A\_{N-2}\$ and is processed last. This gives \$(N-1)!\$ possibilities. There is no overlap between this case and the above because the numbers are guaranteed unique.
If the maximum element is at the third last position, then it depends on the last two elements. If the last element is larger than the second last element, it is treated as the maximum, which fails. There are \$(N-1)!\$ cases, and we can match them by identical first \$(N-3)\$ elements with one case going \$\cdots,max,A,B\$ and the other going \$\cdots,max,B,A\$. Exactly one of these is valid and not the other, so there are \$\frac{(N-1)!}{2}\$ cases.
In general, if the maximum element has \$k\$ elements after it, then the rest of the list must be strictly descending. There is exactly one case for each set of last \$k\$ elements out of the \$k!\$ permutations.
Thus, the answer is \$\frac{(N-1)!}{0!}+\frac{(N-1)!}{1!}+\cdots+\frac{(N-1)!}{(N-1)!}\$. This is [OEIS A000522](http://oeis.org/A000522).
This is equal to \$\frac{\frac{N!}{0!}+\frac{N!}{1!}+\cdots+\frac{N!}{(N-1)!}}{N}\$, which is \$\frac{(N\times(N-1)\times(N-2)\times\cdots\times 1+N\times(N-1)\times(N-2)\times\cdots\times 2+\cdots+N}{N}\$, which is the sum of the cumulative product of the list \$[N,N-1,\cdots,2,1]\$, divided by N.
```
RU×\S:
R       [1, 2, ..., N]
 U      reversed
   \    cumulative
  ×     product
    S   sum
     :  divided by (N)
```
Having MathJax is really nice :D
Note that the list literally does not matter. All we need to know is N.
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 44 bytes
```
K`;
"$+"+`(.*);(.*)
$.(_$1*);$.(_$1*$2*
.*;
```
[Try it online!](https://tio.run/##K0otycxLNPz/3zvBmktJRVtJO0FDT0vTGkRwqehpxKsYAnlQhoqRFpeeljXX//@GBgA "Retina – Try It Online") Explanation:
```
K`;
```
Replace `N` with a counter and output (these should be decimal 0, but the empty string works here).
```
"$+"+`
```
Repeat `N` times...
```
(.*);(.*)
$.(_$1*);$.(_$1*$2*
```
... multiply the output by the counter and increment both.
```
.*;
```
Delete the loop counter.
Previous 47 bytes including modulo 107:
```
K`;
"$+"{`(i*);(j*)
i$1;j$.1*$2
)`(\w{107})*
j
```
[Try it online!](https://tio.run/##K0otycxLNPz/3zvBmktJRVupOkEjU0vTWiNLS5MrU8XQOktFz1BLxYhLM0Ejprza0MC8VlOLiyvr/38jAwA "Retina – Try It Online") Explanation:
```
K`;
```
Replace `N` with a counter and output (both initially 0).
```
"$+"{`
)`
```
Repeat `N` times...
```
(i*);(j*)
i$1;j$.1*$2
```
... multiply the output by the counter and increment both...
```
(\w{107})*
```
... and reduce modulo 107.
```
j
```
Convert the output to decimal.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~8~~ ~~5~~ 4 bytes
-1 byte thanks to @KevinCruijssen
Implementation of @Neil's algorithm.
```
GNP>
```
Explanation:
```
G    for loop from 1 to input 
 N   push current iteration
  P  multiply the stack; in the first iteration there's only 1 element (1)
   > increment
```
[Try it online!](https://tio.run/##yy9OTMpM/f/f3S/A7v9/QwMA "05AB1E – Try It Online")
[Answer]
# JavaScript (ES6), ~~19~~ 18 bytes
*A shorter version suggested by [@Neil](https://codegolf.stackexchange.com/users/17602/neil)*  
*Saved 1 byte thanks to [@Jitse](https://codegolf.stackexchange.com/users/87681/jitse)*
```
f=n=>n&&--n*f(n)+1
```
[Try it online!](https://tio.run/##FYtBDkAwFAX3TvEXIq2mwpo6SxtUiLwviE3Ts1etZhYzu3vdPV3b@WjwvKTkDcyIqtIatReQqkueLwEy1PUEGjLbLEpJCgXRxLj5WJqDV2GdKAOizG0Z/jla2RcxfQ "JavaScript (Node.js) – Try It Online")
Implements the following formula from [A000522](http://oeis.org/A000522):
$$\cases{a\_0=1\\
a\_{n}=n\cdot a\_{n-1} + 1,&n>0}$$
Turned into:
$$\cases{a\_0=0\\
a\_{n}=(n-1)\cdot a\_{n-1} + 1,&n>0}$$
---
# JavaScript (ES6), 35 bytes
This is a port of [@HyperNeutrino's answer](https://codegolf.stackexchange.com/a/194804/58563).
Takes only \$n\$ as input, as per [this consensus](https://codegolf.meta.stackexchange.com/a/12442/58563).
```
n=>(g=n=>n&&(p*=n)+g(n-1))(n,p=1)/n
```
[Try it online!](https://tio.run/##DYrBDoIwEAXvfMUeCNm1ovYM67fQIG005LUB46Xpt9deZuYwH/dz53q803dEfG3Va4U@OWgjhoHTRSEmMEYrwrgmtXJH9fFgkJKdCDQ3P1oYI5Q7ojXijPt222PgxXGfUaS9ffYMKYtMXal/ "JavaScript (Node.js) – Try It Online")
[Answer]
# [Python 3](https://docs.python.org/3/), 28 bytes
```
f=lambda n:n and~-n*f(n-1)+1
```
[Try it online!](https://tio.run/##DcoxDoAgDAXQ3VN0pApD40biYWoUJdEPISwuXr365leffhbMZmm59F43JUSQYnsDxuQQhCexVBqBMqgpjt2JF@E4UG0Z3cHTH5ntAw "Python 3 – Try It Online")
Python port of [Neil](https://codegolf.stackexchange.com/users/17602/neil)'s algorithm.
[Answer]
# [R](https://www.r-project.org/), 28 bytes
```
n=scan();sum(cumprod(n:1))/n
```
[Try it online!](https://tio.run/##K/r/P8@2ODkxT0PTurg0VyO5NLegKD9FI8/KUFNTP@@/ocH//wA "R – Try It Online")
R port of [@HyperNeutrino’s algorithm](https://codegolf.stackexchange.com/a/194804/43328). 
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 12 bytes
```
×\∘⌽∘⍳∘≢+.÷≢
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT/////D0mEcdMx717AWRvZtBZOcibb3D24HU/7RHbRMe9fY96pvq6f@oq/nQeuNHbROBvOAgZyAZ4uEZ/D/t0AoNoD5TTRBpBiYNDTQB "APL (Dyalog Unicode) – Try It Online")
-4 bytes thanks to the change in specifications;
-3 bytes thanks to @Adám
Train that implements [@HyperNeutrino's formula](https://codegolf.stackexchange.com/a/194804/74163), so go upvote their answer.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~69~~ ~~62~~ 60 bytes
Following the consensus in C;
Updated to the most golfed solution thanks to contributions from Arnauld and FryAmTheEggman.
mod 107 has been removed from the rules, I was being too tricky. Thanks for the edit Arnauld.
```
c,o,d,e;f(n){for(e=n;n--;c+=o)for(d=e,o=1;d>n;)o*=d--;c/=e;}
```
[Try it online!](https://tio.run/##Nc3BCsIwDAbg@56iDJRGU3TnEN9lJK3sYCLT29iz11Yxp5/v/yGS7iK1CjoqZirRYCu@xsxGlhLJmR06KGd0nkhvRuAn1l5eONNeF3uHx7xYhGEbQrsORt/4ktlKHA86Yjga/PC5tsVf@8vme52uHw "C (gcc) – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt) [`-x`](https://codegolf.meta.stackexchange.com/a/14339/), 6 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
ÆÉ /Xl
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&flags=LXg&code=xskgL1hs&input=Mw)
[Answer]
# [Ruby](https://www.ruby-lang.org/), 24 bytes
```
f=->n{n<1?1:f[n-=1]*n+1}
```
[Try it online!](https://tio.run/##KypNqvz/P81W1y6vOs/G0N7QKi06T9fWMFYrT9uw9r@GoZ6eoYGmXm5iQXVNRY1CQWlJsYKScnVFrYJydVp0RWytUu1/AA "Ruby – Try It Online")
Using the formula from [OEIS A000522](https://oeis.org/A000522)
]