SHLGOOD

Xét \(x = (x_{1}, x_{2}, . . . , x_{m})\) là một dãy số. Phép dịch trái là chuyển phần tử đầu của dãy xuống cuối dãy. Dãy \(x\) sau khi thực hiện dịch trái \(k\) lần là \((x_{k+1}, x_{k+2}, . . . , x_{m}, x_{1}, x_{2}, . . . , x_{k})\). Dãy \(x\) được gọi là shlgood nếu \(m\) chẵn và có thể dịch trái một số lần (có thể là \(0\) lần) sao cho \(\frac{m}{2}\) phần tử đầu của dãy lớn hơn hẳn \(\frac{m}{2}\) phần tử cuối của dãy, tính từ trái sang phải. Cụ thể, dãy \(x\) là shlgood nếu tồn tại số nguyên không âm \(k\) sao cho sau khi dãy \(x\) dịch trái \(k\) lần, ta thu được dãy \(y\) thoả mãn \(y_{i} > y_{j}\) \(∀1 ≤ i ≤ \frac{m}{2} < j ≤ m\).

Cho dãy số nguyên \(a = (a_{1}, a_{2}, . . . , a_{n})\), hãy đếm số dãy con liên tiếp của a là dãy shlgood.

Input

• Dòng đầu tiên chứa số nguyên dương: \(n\);

• Dòng tiếp theo chứa \(n\) số nguyên: \(a_{1}, a_{2}, . . . , a_{n}\)

Output

Ghi một số nguyên duy nhất là số dãy con liên tiếp là dãy shlgood của \(a\).

Example

6
1 3 2 6 4 5

7

Scoring

• Trong tất cả các test: \(1 ≤ n ≤ 5 × 10^5, −10^9 ≤ a_{i} ≤ 10^9\).

• Có \(12\%\) số test với \(n ≤ 500\);

• Có \(24\%\) số test với \(n ≤ 5000\);

• Có \(20\%\) số test với \(a_{i}\) đôi một phân biệt;

• Có \(44\%\) số test với ràng buộc gốc.