Cuộc hội ngộ Oasis (Oasis Reunion)

Nguồn: Baekjoon Online Judge

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ người đứng thành một hàng, mỗi người có một chiều cao. Hai người có thể nhìn thấy nhau nếu mọi người đứng giữa họ đều không cao hơn người thấp hơn trong hai người đó. Hãy đếm số cặp người có thể nhìn thấy nhau.

Input

Dòng đầu chứa $N$. Mỗi trong $N$ dòng tiếp theo chứa chiều cao của một người theo thứ tự trong hàng.

Output

In số cặp người có thể nhìn thấy nhau.

Subtask

• Subtask 1 (20 điểm): $1\le N\le2000$; các điều kiện khác giữ nguyên.
• Subtask 2 (30 điểm): $1\le N\le5\cdot10^5$ và mọi chiều cao đôi một khác nhau.
• Subtask 3 (50 điểm): $1\le N\le5\cdot10^5$, $1\le H_i<2^{31}$.

Ví dụ

Input

7
2
4
1
2
2
5
1

Output

10

Giải thích

Đánh số người từ $1$ đến $7$, với chiều cao lần lượt là $2,4,1,2,2,5,1$.

Các cặp nhìn thấy nhau là:

(1,2), (2,3), (2,4), (2,5), (2,6), (3,4), (4,5), (4,6), (5,6), (6,7).

Ví dụ, cặp $(2,5)$ có chiều cao $4$ và $2$; những người ở giữa có chiều cao $1$ và $2$, đều không vượt quá người thấp hơn của cặp là $2$, nên cặp này nhìn thấy nhau. Ngược lại, người $1$ và người $3$ không nhìn thấy nhau vì người $2$ ở giữa cao $4$, lớn hơn người thấp hơn của cặp.

Có đúng $10$ cặp hợp lệ, nên chương trình in 10.