Một mảng a₁, a₂, …, aₙ được gọi là FANTABULOUS nếu phần tử có giá trị lớn thứ 2 nằm ở bên trái phần tử có giá trị lớn nhất.

Ví dụ:

a = [1, 2, 13, 10, 15]

là một mảng FANTABULOUS vì phần tử lớn thứ 2 là 13 nằm ở bên trái phần tử lớn nhất là 15.

Gọi x là chỉ số của phần tử lớn thứ 2, y là chỉ số của phần tử lớn nhất. Cặp (x, y) được gọi là FANTABULOUS PAIR.

Với ví dụ trên, ta có:

(x, y) = (3, 5)

Chú ý: Dữ liệu đảm bảo n phần tử phân biệt!

Yêu cầu: Cho mảng A gồm n số nguyên dương a₁, a₂, …, aₙ. Hãy đếm số lượng FANTABULOUS PAIRS khác nhau của tất cả các đoạn con của mảng A.

INPUT

• Dòng đầu tiên chứa số nguyên dương n (1 ≤ n ≤ 10⁶);
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁹).

OUTPUT

Ghi ra một số nguyên là số lượng FANTABULOUS PAIRS khác nhau.

Ví dụ

Sample Input

4
1 3 2 4

Sample Output

3

Giải thích

Các đoạn con tạo ra các FANTABULOUS PAIRS là:

[1, 3]       -> (a, b) = (1, 2)
[2, 4]       -> (a, b) = (1, 2)
[3, 2, 4]    -> (a, b) = (1, 3)
[1, 3, 2, 4] -> (a, b) = (2, 4)

Các cặp khác nhau là:

(1, 2)
(1, 3)
(2, 4)

Vậy có 3 cặp FANTABULOUS PAIRS khác nhau.