Centre for Gifted Education - Hanoi university of Technology

Trước khi giải bài tập này các bạn cần có 1 khái niệm cũng như các phương thức của nó. Khái niệm về Binary Index Tree

Xét bài toán:

Cho một dãy số a₁.. a_N. Một nghịch thế là một cặp số u, v sao cho u < v và a_u > a_v. Nhiệm vụ của bạn là đếm số nghịch thế.

Input

• Dòng đầu ghi số nguyên dương N.
• N dòng sau mỗi dòng ghi một số a_i ( 1 ≤ i ≤ N ).

Output

Ghi trên một dòng số M duy nhất là số nghịch thế.

Giới hạn

• 1 ≤ N ≤ 60000
• 1 ≤ a_i ≤ 60000

Example

Input:
3
3
1
2

Output:
2