Problem Description

Input Format

Input is given from the standard input in the following format:

$ N $ $ p_1 $ $ p_2 $ ... $ p_N $

Output Format

Print the answer.

Sample Input and Output

Sample Input #1

4
4 2 3 1

Sample Output #1

3

Sample Input #2

4
4 3 2 1

Sample Output #2

6

Sample Input #3

7
7 6 3 4 1 2 5

Sample Output #3

36

Sample Input #4

30
30 4 26 15 21 19 14 8 12 7 16 20 2 5 25 13 3 23 18 29 10 27 1 28 9 6 11 24 22 17

Sample Output #4

321470237

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq N \leq 2 \times 10^5$
• $ p_1 = N $
• $ p_1, p_2, ..., p_N $ is a permutation of $\{1, ..., N\}$

Explanation

Explanation

Sample Explanation 1

The ways to produce this permutation are as follows, which are 3 in total:
- $\{4\} \rightarrow \{4, 3\} \rightarrow \{4, 2, 3\} \rightarrow \{4, 2, 3, 1\}$
- $\{4\} \rightarrow \{4, 3\} \rightarrow \{4, 3, 1\} \rightarrow \{4, 2, 3, 1\}$
- $\{4\} \rightarrow \{4, 1\} \rightarrow \{4, 3, 1\} \rightarrow \{4, 2, 3, 1\}$

见题面 Input 部分

见题面 Output 部分