Alice tạo dãy số nguyên \(a_1, a_2, \dots, a_N\), cô cần thống kê số bộ ba chỉ số \((i, j, k)\) thỏa mãn hai điều kiện sau:

1. \(1 \le i < j < k \le N\);
2. \(a_i \le a_j \ge a_k\) hoặc \(a_i \ge a_j \le a_k\).

Yêu cầu: Cho dãy gồm \(N\) số nguyên \(a_1, a_2, \dots, a_N\), hãy đếm số lượng bộ ba thỏa mãn.

Input

• Dòng đầu chứa số nguyên dương \(N\) (\(N \le 3 \cdot 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(|a_i| \le 10^9\)).

Output

• Ghi ra một số nguyên duy nhất là số lượng bộ ba thỏa mãn.

Example

3
1 2 3

0

4
1 3 2 4

2

4
1 1 1 1

4

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(N = 3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \le 300\).
• Subtask \(3\) (\(30\%\) số điểm): \(N \le 3000\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc nào thêm.