Mountain Climbing Game

There are $N$ locations in a row, numbered $1,2,\ldots,N$ from left to right. Location $i$ has height $A_i$. The sequence $A$ is a permutation of the integers from $1$ through $N$.

Dadas and Ttas choose two starting locations $l<r$. Dadas places his piece at $l$, and Ttas places his piece at $r$. They then alternate turns, with Dadas moving first.

When Dadas is currently at $l$ and Ttas is currently at $r$, the rules are:

• On Dadas's turn, choose a location $i$ with $l<i<r$ and $A_i>A_l$, then move his piece there. His new position is .

Thus, a piece may move only to a higher location strictly between the two pieces. A move may skip locations, but may not land on or cross the other piece. After each move, use the pieces' current positions to determine which moves are available.

A player who has no legal move on their turn loses. Passing a turn when a legal move exists is not allowed.

For example, let the heights be $(2,1,4,3)$ and the initial positions be $(l,r)=(1,4)$. Dadas can move from location $1$, of height , to location , of height . The pieces are now at locations and . There is no location between them, so Ttas cannot move on his turn and Dadas wins.

Both players play optimally to win. Find the number of starting pairs $(l,r)$ for which Dadas wins, where $1\leq l<r\leq N$.

The input is given in the following format.

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

For each test case, print the number of starting pairs $(l,r)$ for which Dadas wins on its own line.

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