Teacher Seat Dissatisfaction

The principal has published a seating chart on the campus website where n teachers are arranged from left to right, and initially, every teacher is satisfied with his/her seat. However, during a meeting the principal accidentally shuffles the seating chart, upsetting the teachers.

The teachers do not mind moving far from their original positions, but they are upset about the order of pairs. Specifically, for any pair of teachers \(a\) and \(b\) such that originally teacher \(a\) was to the left of teacher \(b\) (i.e. \(a < b\) when teachers are labelled from 1 to \(n\)) but in the new seating arrangement teacher \(a\) appears to the right of teacher \(b\), this pair contributes 1 unit of dissatisfaction.

Your task is to compute the total dissatisfaction value, which is exactly the number of inversion pairs in the new seating order.

Note: The teachers are originally arranged in natural order \(1, 2, \dots, n\), and the new seating order is given as a permutation of these numbers.

inputFormat

The first line contains an integer \(n\) representing the number of teachers. The second line contains \(n\) distinct integers which represent the new seating order of the teachers. Initially, the teachers were arranged in increasing order \(1, 2, \dots, n\).

outputFormat

Output a single integer which is the total dissatisfaction value (i.e. the number of inversion pairs) among the teachers.

sample

3
1 2 3

0