Problem Description

After completing the research on the ancient Yuezhou disc cipher, archaeologist Xiaobu arrived in the western part of South America. It is said that a long time ago, two tribes lived on this land, one worshiping lightning and the other worshiping mountains, using the shapes of lightning and peaks as their respective totems.

Xiaobu's team discovered a massive mural in a cave, marked with \( N \) points. Measurements revealed that the horizontal and vertical positions of these \( N \) points were pairwise distinct. Xiaobu believes that the information contained in this mural is only related to the relative positions of these \( N \) points. Therefore, let's assume the coordinates are \((1, y_1), (2, y_2), \ldots, (n, y_n)\), where \( y_1 \sim y_n \) is a permutation of \( 1 \sim N \).

Xiaobu's team plans to study how many totems are included in this mural. The definition of the lightning totem is illustrated below (the form of the totem is only related to the relative size arrangement of 4 vertical coordinates):

That is, \( 1 \leq a < b < c < d \leq N, y_a < y_c < y_b < y_d \).

The mountain-worshipping tribe has two clans, so there are two forms of mountain totems, with the left one being Type A and the right one being Type B (similarly, the form of the totem is only related to the arrangement of the sizes of 4 vertical coordinates):

That is, \( 1 \leq a < b < c < d \leq N, y_a < y_b < y_d < y_c \).

That is, \( 1 \leq a < b < c < d \leq N, y_a < y_d < y_c < y_b \).

Xiaobu's team wants to know the difference in the number of totems between the two tribes. Therefore, in this problem, you need to help Xiaobu's team write a program to calculate the difference between the number of lightning totems and the number of mountain totems. Since this value may be large in absolute value, you only need to output the remainder of this value divided by \( 16777216 \) (note that the remainder must be positive, for example, the remainder of \(-1\) divided by \( 16777216 \) is \( 16777215 \)).

Input Format

The first line of the input file totem.in contains an integer \( N \), the number of points.
The next line contains \( N \) integers, respectively \( 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 Format

The output file totem.out contains only one number, which is the difference between the number of lightning totems and the number of mountain totems modulo \( 16777216 \).

Sample Input and Output

Sample Input #1

5
1 5 3 2 4

Sample Output #1

0

Sample Input #2

4
1 2 4 3

Sample Output #2

16777215

Notes/Hints

[Sample Explanation]

In Sample 1, there is 1 lightning totem (\(1324\)) and 1 Type B mountain totem (\(1532\)).

In Sample 2, there is only 1 Type A mountain totem (\(1243\)), so the difference is \(-1\), and the answer is \(16777215\).

[Data Size]

For 10% of the data, \( N \leq 600 \);

For 40% of the data, \( N \leq 5000 \);

For 100% of the data, \( N \leq 200000 \).

见题面 Input 部分

见题面 Output 部分