Counting Handshakes

There are N students in a class, with student IDs ranging from 0 to N-1. In a particular class session, the teacher organizes a handshake game by specifying an order in which the students enter the classroom. When a student enters, they shake hands with every student already present who has a smaller student ID than their own.

Determine the total number of handshakes that occur.

Hint: You can implement a merge sort based approach to count the required pairs. Note that if we define an inversion as a pair (i, j) where i < j and arr[i] > arr[j], then the number of handshake pairs (where arr[i] < arr[j]) is given by:

[ \text{handshakes} = \frac{N(N-1)}{2} - \text{inversions} ]

inputFormat

The first line contains an integer N (1 ≤ N ≤ 10⁵), representing the number of students. The second line contains N space-separated integers, which is a permutation of numbers from 0 to N-1, representing the order in which the students enter the classroom.

outputFormat

Output a single integer: the total number of handshakes.

sample

4
0 1 2 3

6