P4528 [CTSC2008] Totem

After completing the study of the Guyuezhou (Gu Yue Zhou) disk cipher, archaeologist Xiao Bu arrived at the west of the South American continent. It is said that long ago two tribes lived on this land: one worshiped lightning, the other worshiped mountains, and they used the shapes of lightning and peaks as their totems. Xiao Bu’s team discovered a huge mural in a cave. The mural marks $N$ points, and measurements show that the horizontal and vertical coordinates of these $N$ points are pairwise distinct. Xiao Bu believes the information contained in the mural depends only on the relative positions of these $N$ points, so we may set the coordinates as $(1, y_1), (2, y_2), \ldots, (N, y_N)$, where $y_1 \sim y_N$ is a permutation of $1 \sim N$. The team plans to study how many totems are contained in the mural. The definition of a lightning totem is illustrated below (the totem’s type depends only on the relative order of the four $y$-values):  That is, $1 \le a < b < c < d \le N,\ y_a < y_c < y_b < y_d$. The mountain-worship tribe has two clans, so there are two peak totem types, A on the left and B on the right (again, the totem’s type depends only on the relative order of the four $y$-values):  That is, $1 \le a < b < c < d \le N,\ y_a < y_b < y_d < y_c$. That is, $1 \le a < b < c < d \le N,\ y_a < y_d < y_c < y_b$. Xiao Bu’s team wants to know the difference between the counts of the two tribes’ totems. In this problem, you need to compute the number of lightning totems minus the number of peak totems. Since the absolute value of this number can be large, output the result modulo $16777216$ (the remainder must be positive; for example, the remainder of $-1$ modulo $16777216$ is $16777215$).

The first line contains an integer $N$, the number of points. The second line contains $N$ integers $y_1, y_2, \ldots, y_N$. It is guaranteed that $y_1, y_2, \ldots, y_N$ is a permutation of $1 \sim N$.

Output a single integer, the remainder modulo $16777216$ of the difference between the number of lightning totems and the number of peak totems.

[Sample Explanation] In Sample 1, there is 1 lightning totem (1324) and 1 type B peak totem (1532). In Sample 2, there is only one type A peak totem (1243), so the difference is $-1$, and the answer is $16777215$. [Constraints] - For $10\%$ of the testdata, $N \le 600$. - For $40\%$ of the testdata, $N \le 5000$. - For $100\%$ of the testdata, $N \le 200000$. Translated by ChatGPT 5