Інверсією в перестановці \(p_1, p_2, ..., p_N\) називається пара \((i, j)\) така, що \(i < j\) і \(p_i > p_j\).

Назвемо мега-інверсією в перестановці \(p_1, p_2, ..., p_N\) трійку \((i, j, k)\) таку, що \(i < j < k\) і \(p_i > p_j > p_k\).

Придумайте алгоритм швидкого підрахунку кількості мега-інверсій у перестановці.

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

Перший рядок вхідного файлу містить ціле число \(N\) \((1 \le N \le 100\,000)\).

Наступні \(N\) чисел описують перестановку: \(p_1, p_2, ..., p_N\) \((1 \le p_i \le N\)), всі \(p_i\) попарно різні.

Числа розділяються пробілами та/або перекладами рядків.

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

Єдиний рядок вихідного файлу повинен містити одне число, яке дорівнює кількості мега-інверсій у перестановці \(p_1, p_2, ..., p_N\).

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

4
4 3 2 1

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

4