P8275 [USACO22OPEN] 262144 Revisited P

Bessie likes to download games to play on her phone, although she does find it rather difficult to use a small touchscreen with her big hooves. She is especially obsessed with the game she is currently playing. The game starts with a sequence $a_1,a_2,\ldots,a_N$ of $N$ positive integers in the range $1\ldots 10^6$ ($2\le N\le 262,144$). In one move, Bessie can take two adjacent numbers and replace them with a single number that is greater than the maximum of the two numbers (for example, she can replace the adjacent pair $(5,7)$ with $8$). The game ends after $N-1$ moves, when only one number remains. The goal of the game is to **minimize** this final number. Bessie knows this game is too easy for you. So your task is not only to play the game optimally on $a$, but to play it on every contiguous subarray of $a$. Output the sum of the minimum possible final numbers over all $\frac{N(N+1)}{2}$ contiguous subarrays of $a$.

The first line of input contains $N$. The second line contains $N$ space-separated integers, representing the input sequence.

Output one line containing the required sum.

There are a total of $\frac{6\cdot 7}{2}=21$ contiguous subarrays. For example, the minimum possible final number for the contiguous subarray $[1,3,1,2,1]$ is $5$, which can be achieved by the following sequence of operations: ``` Initial -> [1,3,1,2,1] Merge 1&3 -> [4,1,2,1] Merge 2&1 -> [4,1,3] Merge 1&3 -> [4,4] Merge 4&4 -> [5] ``` Below are the minimum possible final numbers for each contiguous subarray: ``` final(1:1) = 1 final(1:2) = 4 final(1:3) = 5 final(1:4) = 5 final(1:5) = 5 final(1:6) = 11 final(2:2) = 3 final(2:3) = 4 final(2:4) = 4 final(2:5) = 5 final(2:6) = 11 final(3:3) = 1 final(3:4) = 3 final(3:5) = 4 final(3:6) = 11 final(4:4) = 2 final(4:5) = 3 final(4:6) = 11 final(5:5) = 1 final(5:6) = 11 final(6:6) = 10 ``` [Subtask Properties] - Testcases 2-3 satisfy $N\le 300$. - Testcases 4-5 satisfy $N\le 3000$. - In testcases 6-8, all values in the input sequence are at most $40$. - In testcases 9-11, the input sequence is non-decreasing. - Testcases 12-23 have no additional constraints. Translated by ChatGPT 5