Hội các học sinh chuyên Tin vừa chế tạo thành công một cỗ máy thời gian.
Họ quay về năm 2022 và 2028 để xem có gì thú vị.

Các bạn phát hiện ra là ở hai khóa này đều có một bạn nữ đọc tên khá giống nhau, ta tạm gọi hai bạn này là HKĐ. Nhưng mà hiện tại chỉ kết luận hai bạn chỉ giống nhau ở cái tên thôi

Các nhà sinh học của hội đã vô tình thu thập được mẫu gen của hai bạn. Các nhà mật mã học quyết định mã hóa bộ gen dưới dạng một hoán vị độ dài \(n\), và đếm xem có bao nhiêu đoạn đầu cuối trong mỗi bộ gen. Nếu số lượng gần bằng nhau thì có lẽ hai bạn được gắn kết với nhau qua một chiều không gian thứ 5.

Cho một bộ gen được mã hóa dưới dạng một hoán vị A có độ dài \(n\): \(A_1, A_2, A_3, \dots, A_n, (A_i \le n, A_i \ne A_j \forall i \ne j)\).
Một đoạn \((l, r)\) trong dãy \(A\) là gồm các phần tử liên tiếp từ \(l\) tới \(r\) \((l \le r)\), tức \(A_l, A_{l+1}, \dots, A_{r-1}, A_r\).
Một đoạn \((l, r)\) được gọi là đoạn đầu cuối nếu cả giá trị nhỏ nhất và lớn nhất của đoạn đều nằm ở đầu và cuối đoạn, tức là nằm ở cả hai vị trí \(l\) và \(r\).

Ví dụ như \([2, 6, 5, 9]\) là đoạn đầu cuối vì giá trị nhỏ nhất của đoạn là \(2\), giá trị lớn nhất của đoạn là \(9\), và cả hai giá trị này đều nằm ở đầu đoạn và cuối đoạn.
Dãy \([2, 4, 3]\) thì không vì giá trị lớn nhất của đoạn là \(4\) nằm ở giữa đoạn.

Bạn hãy tính số đoạn đầu cuối trong hoán vị \(A\) nhé.

Input

• Dòng thứ nhất chứa số \(n\)
• Dòng thứ hai chứa \(n\) số của hoán vị \(A\): \(A_1, A_2, \dots, A_n\).

Output

In ra số lượng dãy đầu cuối của bộ gen \(A\).

Sample

Input 1:

8
2 5 1 4 3 8 7 6

Output 1:

17

Input 2:

11
1 2 3 4 5 6 10 7 11 8 9

Output 2:

42

Subtask

• Subtask 1 (12%): \(A_i < A_{i+1} \forall i \in [1, n)\), hoặc \(A_i > A_{i+1} \forall i \in [1, n)\)
• Subtask 2 (20%): \(n \le 500\)
• Subtask 3 (28%): \(n \le 5000\)
• Subtask 4 (40%): \(n \le 5 \times 10^5\)