Dãy con Manhattan

Cho hai điểm $p=(x_p,y_p)$ và $q=(x_q,y_q)$ trên mặt phẳng. Khoảng cách Manhattan giữa chúng được định nghĩa là:

$$d(p,q)=|x_p-x_q|+|y_p-y_q|.$$

Ba điểm $p$, $q$, $r$ tạo thành một bộ ba xấu nếu $d(p,r)=d(p,q)+d(q,r)$.

Một dãy $b_1,b_2,\dots ,b_m$ được gọi là tốt nếu không tồn tại ba chỉ số phân biệt $i,j,k$ sao cho ba điểm $(b_i,i)$, $(b_j,j)$, $(b_k,k)$ tạo thành một bộ ba xấu. Theo định nghĩa, mọi dãy có độ dài $1$ hoặc $2$ đều tốt.

Cho dãy $a_1,a_2,\dots ,a_n$. Hãy đếm số dãy con liên tiếp tốt của $a$. Một dãy con liên tiếp là dãy có dạng $a_l,a_{l+1},\dots ,a_r$ với $1\le l\le r\le n$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$ ($1\le t\le 5000$) — số bộ test.
• Mỗi bộ test gồm:
  • Dòng đầu: số nguyên $n$ ($1\le n\le 2·{10}^5$) — độ dài dãy.
  • Dòng thứ hai: $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^9$).

Tổng giá trị $n$ qua tất cả bộ test không vượt quá $2·{10}^5$.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên là số dãy con liên tiếp tốt của $a$.

Ràng buộc

• $1\le t\le 5000$
• $1\le n\le 2·{10}^5$
• $1\le a_i\le {10}^9$
• Tổng $n$ qua các bộ test $\le 2·{10}^5$.

Ví dụ