Có \(n\) người xếp hàng dọc đánh số từ \(1\) tới \(n\) từ đầu hàng tới cuối hàng, người thứ \(i\) có chiều cao là \(h_i\). Ta nói hai người \(i,j\) nhìn thấy nhau nếu giữa hai người đó không tồn tại người nào khác có chiều cao \(\geq \min⁡\{h_i,h_j\}\), hay nói cách khác, tất cả những người đứng giữa người \(i\) và người \(j\) (nếu có) đều có chiều cao thấp hơn cả hai người này.

Yêu cầu: Đếm số cặp chỉ số \(i,j\) \((i<j)\) mà hai người \(i,j\) nhìn thấy nhau.

Input

Vào từ file văn bản PAIRS.INP

• Dòng 1 chứa số nguyên dương \(n \leq 5 \cdot 10^5\).
• Dòng 2 chứa n số nguyên dương \(h_1,h_2,\ldots,h_n\) \((\forall i:h_i \leq 10^6)\) cách nhau bởi dấu cách.

Output

Ghi ra file văn bản PAIRS.OUTmột số nguyên duy nhất là số cặp chỉ số \(i,j\) \((i<j)\) mà hai người \(i,j\) nhìn thấy nhau.

Example

6
2 1 4 3 6 5

7

5
2 2 2 2 2

4

Nguồn: Thầy Lê Minh Hoàng