Dãy số bitonic

Dãy số $b_1, b_2, \ldots, b_k$ được gọi là dãy bitonic nếu $b_1 < b_2 < \cdots < b_i > \cdots > b_k$ với $1 \le i \le k$. Chú ý rằng nếu $i = 1$ thì $b_1 > b_2 > \cdots > b_k$ và dãy $b$ là dãy giảm, còn nếu $i = k$ thì $b_1 < b_2 < \cdots < b_k$ và dãy $b$ là dãy tăng, còn nếu $1 < i < k$ thì các phần từ từ $b_1$ đến $b_i$ tăng dần và các phần tử từ $b_i$ đến $b_k$ giảm dần.

Ví dụ các dãy sau là dãy bitonic:

• 1;
• 1, 2, 3, 2;
• 1, 4, 10;
• 3, 2.

và các dãy sau không là dãy bitonic:

• 1, 1;
• 2, 1, 3.

Cho dãy số $a_1, a_2, \ldots, a_n$. Hãy đếm số cặp $(l, r)$ sao cho $1 \le l \le r \le n$ và dãy $a_l, a_{l+1}, \ldots, a_r$ là dãy bitonic.

Vào từ tệp bit.inp. Dòng đầu tiên chứa số nguyên $n$ ($1 \le n \le 3 \times 10^5$). Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

Ghi ra tệp bit.out một số nguyên là số cặp $(l, r)$ sao cho $1 \le l \le r \le n$ và dãy $a_l, a_{l+1}, \ldots, a_r$ là dãy bitonic.

• Có 40% số test ứng với 40% số điểm thỏa mãn: $n \le 500$;
• 30% số test khác ứng với 30% số điểm thỏa mãn: $n \le 5000$;
• 30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.