After completing his research on the ancient Yuezhou disk cipher, the archaeologist Xiao Bu arrived in the western part of the South American continent. Legend has it that long ago, two tribes lived on this land: one worshipped lightning, and the other worshipped mountains. They used the shapes of lightning and mountain peaks as their respective tribal totems.

Xiao Bu's team discovered a massive mural in a cave, on which $N$ points were marked. Measurements revealed that the horizontal and vertical positions of these $N$ points were all distinct. Xiao Bu believed that the information contained in this mural was only related to the relative positions of these $N$ points. Therefore, we can assume the coordinates are $(1, y_1), (2, y_2), \dots, (n, y_n)$, where $y_1, \dots, y_n$ is a permutation of $1 \dots N$.

Xiao Bu's team intends to study how many totems are contained in this mural. The definition of a lightning totem is illustrated below (the form of a totem depends only on the relative order of the 4 vertical coordinate values):

That is, $a < b < c < d \le N$ and $y_a < y_c < y_b < y_d$.

The tribe that worships mountains has two clans, so there are two forms of mountain totems: type A on the left and type B on the right (similarly, the form of the totem depends only on the relative order of the 4 vertical coordinate values):

That is, $a < b < c < d \le N$ and $y_a < y_b < y_d < y_c$ for type A, and $a < b < c < d \le N$ and $y_a < y_c < y_d < y_b$ for type B.

Xiao Bu's team wants to know the difference between the number of lightning totems and the number of mountain totems among these $N$ points. Therefore, in this problem, you need to help Xiao Bu's team write a program to calculate the number of lightning totems minus the number of mountain totems. Since this value may have a large absolute value, you only need to output the remainder of this value modulo $16777216$ (note that the remainder must be positive; for example, the remainder of $-1$ modulo $16777216$ is $16777215$).

Input

The first line contains an integer $N$, the number of points. The next line contains $N$ integers, $y_1, y_2, \dots, y_n$. It is guaranteed that $y_1, y_2, \dots, y_n$ is a permutation of $1 \dots N$.

Output

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

Examples

Input 1

5
1 5 3 2 4

Output 1

0

Input 2

4
1 2 4 3

Output 2

16777215

Note

In Example 1, there is 1 lightning totem (1324) and 1 type B mountain totem (1532). In Example 2, there is only one type A mountain totem (1243), so the difference is $-1$, and the answer is $16777215$.

Constraints

For $10\%$ of the data, $N \le 600$; For $40\%$ of the data, $N \le 5000$; For $100\%$ of the data, $N \le 200000$.