Totem Difference

After researching the ancient "Guyuet州” disk cipher, the archaeologist Xiao Bu proceeds to the western part of the South American continent. In ancient times, two tribes inhabited this land – one worshipping lightning and the other worshipping mountains – and they used the shape of lightning and mountain peaks as their respective totems.

In a cave, Xiao Bu’s team discovered a huge mural with N marked points. It was measured that the horizontal and vertical positions of these points are all distinct. Therefore, one may assume the coordinates to be (1, y₁), (2, y₂), …, (N, y_N), where y₁,…, y_N is a permutation of {1,2,…,N}.

The team is studying the number of totems present in these N points. The definition of a lightning totem is illustrated below. (Note that the formation of a totem depends only on the relative order of the four vertical coordinates.)

Lightning Totem: indices a, b, c, d (with 1 ≤ a < b < c < d ≤ N) form a lightning totem if \[ y_a < y_c < y_b < y_d. \]

The mountain totems come in two forms, corresponding to two clans. Both forms depend only on the relative order of the four vertical values.

Mountain Totem Type A: For indices a, b, c, d (1 ≤ a < b < c < d ≤ N), it satisfies \[ y_a < y_b < y_d < y_c. \]

Mountain Totem Type B: For indices a, b, c, d (1 ≤ a < b < c < d ≤ N), it satisfies \[ y_a < y_d < y_c < y_b. \]

Your task is to help Xiao Bu’s team compute the difference between the number of lightning totems and the total number of mountain totems. Since the absolute value of this difference can be large, output the answer modulo \(16777216\) (note: the remainder should be positive; for example, \(-1 \bmod 16777216 = 16777215\)).

inputFormat

The first line contains a single integer \(N\). The second line contains \(N\) space-separated integers which form a permutation of \(\{1, 2, \dots, N\}\).

outputFormat

Output a single integer representing the value of (# lightning totems) - (# mountain totems) modulo \(16777216\).

sample

4
1 2 3 4

0