Description

Alice and Bob invented a new game. Given a sequence $\{x_0, x_1, \cdots, x_{n-1}\}$, Alice gets a sequence $\{a_0, a_1, \cdots, a_{n-1}\}$, where $a_i$ is the length of the longest increasing subsequence ending at $x_i$; Bob gets a sequence $\{b_0, b_1, \cdots, 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_i\}$, and Bob’s score is the sum of the sequence $\{b_i\}$.

Input Format

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

Output Format

Output a single line indicating the highest score Bob can obtain given the sequence $\{a_i\}$.

4
1 2 2 3

5

4
1 1 2 3

5

Hint

Constraints

For $30\%$ of the testdata, $n \le 1000$.

For $100\%$ of the testdata, $n \le 10^5$.

Translated by ChatGPT 5