Đồi và thung lũng

Cho dãy $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Một chỉ số $j$ (với $2\le j\le n-1$) được gọi là đỉnh đồi nếu $a_j>a_{j+1}$ và $a_j>a_{j-1}$; được gọi là thung lũng nếu $a_j<a_{j+1}$ và $a_j<a_{j-1}$.

Độ gồ ghề của dãy là tổng số đỉnh đồi và số thung lũng có trong dãy.

Bạn được phép thay đúng một phần tử của dãy thành một số nguyên tùy ý (không nhất thiết nằm trong khoảng giá trị ban đầu), hoặc giữ nguyên dãy. Hãy tìm độ gồ ghề nhỏ nhất có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa số nguyên $n$.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng độ gồ ghề nhỏ nhất có thể đạt được.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le 3·{10}^5$
• $1\le a_i\le {10}^9$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $3·{10}^5$.

Ví dụ