{"code":"olp3sldoublehead","name":"Vòng sơ loại OLP Miền Trung Tây Nguyên - Đoạn hai đầu","description":"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.
\r\nHọ quay về năm $2022$ và $2028$ để xem có gì thú vị.\r\n\r\nCá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Đ.\r\nNhưng mà hiện tại chỉ kết luận hai bạn chỉ giống nhau ở cái tên thôi\r\n\r\nCá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$.\r\n\r\nCho 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)$.
\r\nMộ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$.
\r\nMộ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$.
\r\n\r\nVí 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.
\r\nDã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.\r\n\r\nBạn hãy tính số đoạn đầu cuối trong hoán vị $A$ nhé.\r\n\r\n

Input

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

Output

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

Scoring

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 8\r\n 2 5 1 4 3 8 7 6\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 17\r\n ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 11\r\n 1 2 3 4 5 6 10 7 11 8 9\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 42\r\n ```","points":100.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}