Constructing Constrained Sequences

You are given an integer n and a sequence of n positive integers \(r_1, r_2, \dots, r_n\). You need to count the number of different integer sequences \(A_1, A_2, \dots, A_n\) satisfying the following conditions:

• \(1 \le A_i \le r_i\) for every \(1 \le i \le n\).
• For every index \(i\) with \(3 \le i \le n\), let \[ L = \max\{ A_j : 1 \le j \le i-2 \text{ and } A_j \le A_{i-1} \} \quad (\text{if such } A_j \text{ exists, otherwise } L=-\infty), \] and \[ R = \min\{ A_j : 1 \le j \le i-2 \text{ and } A_j \ge A_{i-1} \} \quad (\text{if such } A_j \text{ exists, otherwise } R=+\infty). \] Then the element \(A_i\) must satisfy \[ L \le A_i \le R. \]

Two sequences \(A\) and \(B\) are considered different if there is at least one index \(i\) such that \(A_i \neq B_i\). Compute the total number of sequences that satisfy the given conditions.

inputFormat

The first line contains an integer n representing the length of the sequence. The second line contains \(n\) space‐separated positive integers \(r_1, r_2, \dots, r_n\).

outputFormat

Output a single integer — the number of valid sequences.

sample

3
3 3 3

14