지그재그 부분배열

길이가 $n$인 정수 배열 $A$가 주어지고, $A[i]$는 $i$번째 원소이다 ($i = 1, 2, \ldots, n$). $1 \le i \le j \le n$을 만족하는 인덱스 $i, j$에 대해 $A[i, j]$는 $i$번째 원소부터 $j$번째 원소까지 $(j-i+1)$개의 원소로 이루어진 $A$의 부분 배열이다. 이 부분 배열의 길이는 $(j-i+1)$이다. 예를 들어 $A = [2, 2, 1, 3, 2]$이면 $A[2, 3] = [2, 1]$이고 $A[3, 5] = [1, 3, 2]$이다.

길이가 2 이상인 ($i < j$) 부분 배열 $A[i, j]$의 원소가 증가와 감소를 번갈아 반복하면 지그재그 부분 배열이라 한다. 구체적으로 다음 조건 중 하나를 만족해야 한다.

• 조건 1: $i \le k < j$인 모든 $k$에 대해, $(k-i)$가 짝수이면 $A[k] < A[k+1]$이고, 홀수이면 $A[k] > A[k+1]$이다.
• 조건 2: $i \le k < j$인 모든 $k$에 대해, $(k-i)$가 짝수이면 $A[k] > A[k+1]$이고, 홀수이면 $A[k] < A[k+1]$이다.

예를 들어 $A = [2, 2, 1, 3, 2]$일 때 $A[2, 3]$과 $A[3, 5]$는 지그재그 부분 배열이고, $A[1, 2]$와 $A[1, 3]$은 지그재그 부분 배열이 아니다.

Alice는 $A$의 부분 배열 중 지그재그 부분 배열이 몇 개인지 알고 싶어 한다. Alice를 도와 그 개수를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 주어진다. 첫 줄에 $n$이 주어지고, 둘째 줄에 공백으로 구분된 $n$개의 정수가 주어진다.

각 테스트 케이스의 정답, 즉 지그재그 부분 배열의 개수를 한 줄에 하나씩 출력한다.

$1 \le T \le 10$

$1 \le n \le 100{,}000$

$-10^9 \le A[i] \le 10^9$ ($1 \le i \le n$)