Một dãy số nguyên ~a_1,a_2,\dots,a_n~ được gọi là dãy tăng nếu ~a_i>a_{i-1}~ với mọi ~i~. Ví dụ, ~(1,2,3,4,6)~ là một dãy tăng, trong khi ~(2,1,3,4,6)~ thì không.

Một dãy số ~b_1,b_2,\dots,b_n~ được gọi là dãy nửa tăng khi tồn tại một cặp chỉ số ~(l,r)~ có thể bằng nhau sao cho sau khi đảo ngược đoạn con liên tiếp từ ~l~ đến ~r~ của dãy ~b~ (gồm các phần tử ~b_l,b_{l+1},\dots,b_r~) thì dãy thu được là một dãy tăng. Ví dụ, ~(2,1,3,4,6)~ là một dãy nửa tăng vì có thể đảo ngược đoạn con ~(1,2)~ của dãy để tạo thành dãy tăng ~(1,2,3,4,6)~, trong khi ~(2,1,4,3,6)~ thì không.

Bạn được cho một hoán vị độ dài ~n~ (một dãy số mà mỗi số tự nhiên từ ~1~ đến ~n~ xuất hiện đúng một lần). Hãy đếm xem có bao nhiêu đoạn con liên tiếp của hoán vị này là một dãy nửa tăng.

Input

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 10^6)~.

• Dòng tiếp theo gồm ~n~ số nguyên dương ~p_1,p_2,\dots,p_n~ là hoán vị được cho ~(1 \le p_i \le n)~.

Output

Một dòng duy nhất gồm số lượng đoạn con liên tiếp của ~p~ là một dãy nửa tăng.

Scoring

Sample Input 1

5
5 2 4 1 3

Sample Output 1

9

Notes

Các đoạn con liên tiếp sau là các dãy nửa tăng: ~(5),(2),(4),(1),(3),(5,2),(2,4),(4,1),(1,3)~.