Alice and Bob have invented a new game. Given a sequence $\{x_0, x_1, \dots, x_{n-1}\}$, Alice obtains a sequence $\{a_0, a_1, \dots, a_{n-1}\}$, where $a_i$ is the length of the longest increasing subsequence ending at $x_i$. Bob obtains a sequence $\{b_0, b_1, \dots, b_{n-1}\}$, where $b_i$ is the length of the longest decreasing subsequence starting at $x_i$. Alice's score is the sum of the sequence $\{a_0, a_1, \dots, a_{n-1}\}$, and Bob's score is the sum of the sequence $\{b_0, b_1, \dots, b_{n-1}\}$.

Input

The first line contains $n$, and the second line contains the sequence $\{a_0, a_1, \dots, a_{n-1}\}$. It is guaranteed that the sequence $a$ can be obtained from at least one permutation of $1$ to $n$.

Output

Output a single line representing the maximum score Bob can obtain.

Data Range

For $30\%$ of the data, $n \le 1000$. For $100\%$ of the data, $n \le 10^5$.

Examples

Input 1

4
1 2 2 3

Output 1

5

Input 2

4
1 1 2 3

Output 2

5