산 오르기 게임

일렬로 놓인 $N$개의 지점이 있다. 왼쪽부터 $1$번, $2$번, $\ldots$, $N$번 지점이며, $i$번 지점의 높이는 $A_i$이다. 수열 $A$는 $1$부터 $N$까지의 정수가 한 번씩 나타나는 순열이다.

다다스와 따스는 서로 다른 두 지점 $l<r$을 골라, 다다스는 $l$번 지점에, 따스는 $r$번 지점에 자신의 말을 놓는다. 이후 다다스부터 시작하여 번갈아 가며 자기 말을 움직인다.

현재 다다스의 말이 $l$번 지점에, 따스의 말이 $r$번 지점에 있을 때, 이동 규칙은 다음과 같다.

• 다다스의 차례에는 $l<i<r$이고 $A_i>A_l$인 지점 를 골라 이동한다. 이동한 뒤 다다스의 위치는 가 된다.

즉, 자기 말보다 높으면서 두 말 사이에 있는 지점으로만 이동할 수 있다. 바로 옆 지점으로 이동할 필요는 없지만, 상대의 말이 있는 지점으로 이동하거나 상대의 말을 넘어갈 수는 없다. 이동할 때마다 두 말의 현재 위치를 기준으로 이동 가능한 지점을 다시 판단한다.

자기 차례에 이동할 수 있는 지점이 없으면 그 사람이 진다. 이동할 수 있는데 차례를 넘기는 것은 허용되지 않는다.

예를 들어 높이가 $(2,1,4,3)$이고 처음 위치가 $(l,r)=(1,4)$라고 하자. 다다스는 높이 $2$인 번 지점에서 높이 인 번 지점으로 이동할 수 있다. 이제 두 말은 번과 번 지점에 있다. 두 말 사이에 지점이 없으므로, 다음 차례인 따스가 이동하지 못해 다다스가 이긴다.

두 사람 모두 이기기 위해 최선의 선택을 한다. 다다스가 이기는 처음 위치의 쌍 $(l,r)$의 개수를 구하여라. 단, $1\leq l<r\leq N$이다.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 다다스가 이기는 처음 위치의 쌍 $(l,r)$의 개수를 한 줄에 출력한다.

• $1\leq T\leq200\,000$.
• $1\leq N\leq200\,000$.
• $1\le A_{}$ ().