Дано масив \(A\), яки містить \(N\) цілих чисел. Знайдіть у масиві кількість інверсій.

Кількість інверсій: для масиву кількість інверсій показує, наскільки далеко (або близько) масив від сортування. Якщо масив уже відсортовано, кількість інверсій дорівнює 0. Якщо масив відсортовано у зворотному порядку, кількість інверсій є максимальною. Формально два елементи a[i] і a[j] утворюють інверсію, якщо a[i] > a[j] і i < j.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\).

Наступний рядок містить \(N\) цілих чисел \(A_i\).

Числа розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести відповідь.

Обмеження

\(1 \le N \le 5 \times 10^5\)

\(1 \le A_i \le 10^6\)

Приклад вхідних даних

5
2 4 1 3 5

Приклад вихідних даних

3

Приклад вхідних даних

5
1 1 1 1 1

Приклад вихідних даних

0