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

Sample Input 1

3
1 2 3

Sample Output 1

0

Sample Input 2

4
1 3 2 4

Sample Output 2

2

Sample Input 3

4
1 1 1 1

Sample Output 3

4