Cho một hoán vị \(p\) gồm \(n\) số nguyên từ \(1\) đến \(n\). Một hoán vị là một dãy gồm \(n\) số nguyên phân biệt từ \(1\) đến \(n\) theo một thứ tự bất kỳ.

Một dãy con liên tiếp (subarray) của hoán vị \(p\), ký hiệu là \(p[l..r]\) (với \(1 \le l \le r \le n\)), được gọi là hợp lệ nếu vị trí của phần tử lớn nhất trong dãy con đó nằm bên phải vị trí của phần tử nhỏ nhất trong dãy con đó.

Hãy đếm số lượng dãy con liên tiếp \(p[l..r]\) hợp lệ trong hoán vị \(p\).

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 10^6\)) — độ dài của hoán vị.
• Dòng thứ hai chứa \(n\) số nguyên \(p_1\), \(p_2\), \(\dots\), \(p_n\) (\(1 \le p_i \le n\)) — các phần tử của hoán vị \(p\). Tất cả các \(p_i\) đôi một khác nhau.

Dữ liệu ra

In ra một số nguyên duy nhất — số lượng dãy con liên tiếp hợp lệ của hoán vị \(p\).

Ví dụ

Giải thích ví dụ

• Ví dụ 1: Các dãy con hợp lệ là \([1\), \(2]\) (min ở \(1\), max ở \(2\)), \([2, 3]\) (min ở \(2\), max ở \(3\)), và \([1, 2, 3]\) (min ở \(1\), max ở \(3\)). Các dãy con có \(l = r\) không hợp lệ vì vị trí max và min trùng nhau.