INVCOUNT

Given a sequence of integers ~a_1~, ~a_2~, ~...~ ~a_N~, find the number of inversions. Two numbers in the sequence ~i~, ~j~ form an inversion if ~i < j~ and ~a_i > a_j~.

For example, in the sequence ~2~, ~8~, ~1~, ~3~, ~10~, there are ~3~ inversions: ~(2,\;1)~, ~(8,\;1)~, and ~(8,\;3)~.

The numbers in the sequence are all distinct from each other.

Input

The first line contains the number ~N~. The next line contains the numbers ~a_1~ ~...~ ~a_N~ separated in pairs by a space.

Output

An integer corresponding to the number of inversions in the sequence.

Constraints

~1 \le N \le 100.000~
~1 \le a_i \le 555.555.555~

Time Limit: 1 sec.
Maximum Available Memory: 16 MB.

Example of Input - Output

STDIN (invcount.in)

5
2 8 1 3 10

STDOUT (invcount.out)

3