P3971 [TJOI2014] Alice and Bob

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\}$.

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 a single line indicating the highest score Bob can obtain given the sequence $\{a_i\}$.

### Constraints For $30\%$ of the testdata, $n \le 1000$. For $100\%$ of the testdata, $n \le 10^5$. Translated by ChatGPT 5