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 \le i < j < k \le N~;
• ~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 \times 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

Một số nguyên là số lượng bộ ba thỏa mãn.

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

Ví dụ

Input 1

3
1 2 3

Output 1

0

Input 2

4
1 3 2 4

Output 2

2

Input 3

4
1 1 1 1

Output 3

4