P16798 [Lanqiao Cup 2026 National B] Token 词元

In March 2026, the China National Committee for Terminology in Science and Technology announced that it would prioritize setting the Chinese translation of the AI term “Token” as “词元”, and put it on trial for the whole society. Since then, the platform where Xiao Lan works has started using “词元” as the official unit for monthly statistics. There are $n$ APIs on the platform, numbered from $1$ to $n$ from left to right. The number of tokens consumed this month by API $i$ is $p_i$. At the end of the month, the platform needs to assign an inspection level for each API for the next month based on token consumption. Each API will be assigned a positive integer inspection level. A higher inspection level means the API needs closer monitoring. However, the platform does not assign inspection levels directly by the absolute value of token consumption, but instead refers to the relative relationships between adjacent APIs. For API $i$, define $c_i$ as the number of adjacent APIs whose token consumption is less than $p_i$. Here, adjacent APIs are those whose indices differ by $1$. That is, API $i$ can only be adjacent to API $i-1$ and API $i+1$. API $1$ only has a right neighbor, and API $n$ only has a left neighbor; all other APIs have both neighbors. Therefore, $c_i \in \{0, 1, 2\}$. Let the inspection level of API $i$ be $a_i$. The platform requires that for any adjacent APIs $i$ and $i+1$: - If $c_i < c_{i+1}$, then $a_i < a_{i+1}$. - If $c_i > c_{i+1}$, then $a_i > a_{i+1}$. - If $c_i = c_{i+1}$, there is no requirement on the relation between $a_i$ and $a_{i+1}$. There may be multiple inspection level assignments that satisfy the rules. Because inspection resources are limited, the platform wants the sum of inspection levels to be as small as possible (i.e., minimize $\sum_{i=1}^{n} a_i$). Now, please help the platform find this minimum value.

The input has two lines. The first line contains a positive integer $n$, representing the number of APIs. The second line contains $n$ integers $p_1, p_2, \ldots, p_n$, where $p_i$ represents the number of tokens consumed this month by API $i$.

Output one line containing a positive integer, representing the minimum possible sum of inspection levels over all APIs, under the condition that all adjacent inspection level requirements are satisfied.

### Constraints For $30\%$ of the testdata, $2 \le n \le 2 \times 10^3$, $1 \le p_i \le 10^5$. For all testdata, $2 \le n \le 2 \times 10^5$, $1 \le p_i \le 10^9$. Translated by ChatGPT 5