Đếm bộ ba

Cho dãy số nguyên dương gồm \(N\) phần tử \(A_1, A_2, \ldots, A_N\).

Yêu cầu: Đếm số lượng bộ ba số nguyên dương (\(x,y,z\)) thỏa mãn:

• \(0<x<y<z\leq N\);

• \(A_x<A_y\) và \(A_y>A_z\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) (\(N\leq 3*10^5\)).

• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1,A_2,…,A_N\) (\(1\leq a_i\leq 10^{18}\)).

Output

• In ra kết quả bài toán là số lượng bộ ba (\(x,y,z\)) thỏa mãn.

Example

5
0 1 1 0 1

2

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Dãy \(A_i\) không giảm (\(A_i\leq A_j\) với \(i<j\)).

• Subtask \(2\) (\(15\%\) số điểm): \(A_i\in [0,1]\).

• Subtask \(3\) (\(15\%\) số điểm): \(A_i\in [0,100]\).

• Subtask \(4\) (\(15\%\) số điểm): \(N\leq 500\).

• Subtask \(5\) (\(15\%\) số điểm): \(N\leq 10000\).

• Subtask \(6\) (\(15\%\) số điểm): \(A_i\in [0,10^5]\).

• Subtask \(7\) (\(15\%\) số điểm): Không có giới hạn gì thêm.