Glass Bridge

Water pollution troubles many large cities, and the ACM metropolis of ICPC country is no exception. Many cities treat sewage before releasing it into a water source, but the ACM metropolis has too little spare land for treatment plants.

The government of the ACM metropolis picked a chemical method instead. It releases a treatment chemical into the rivers around the city to purify the water. The reaction needs sunlight, so every bridge across a river is being rebuilt in glass.

A glass bridge still blocks 50% of the sunlight. Where two glass bridges overlap, only 25% of the sunlight gets through. The chemical needs at least 40% of the sunlight to work, so an overlap is a problem. Overlaps cannot be avoided completely, so the government wants the area below 40% to be as small as possible.

The government plans to build $N$ more bridges over one river. A three level bridge is not buildable, so at most two bridges overlap at any point. The government wants to know how many points are covered by two bridges.

The districts along the river face each other. District 1 sits directly across from district $-1$, district 2 across from district $-2$, and so on. Plan $i$ is a bridge from district $i$ to district $-a_i$. Bridge $i$ and bridge $j$ cross over the river exactly when $i < j$ and $a_i > a_j$. Count the pairs of bridges that cross.

The first line contains the number of test cases $T$. ($1 \le T \le 20$)

Each test case starts with a line holding the number of bridges to build, $N$. ($2 \le N \le 100\,000$)

The next line holds $N$ integers $a_1\ a_2\ \dots\ a_N$ separated by spaces. ($1 \le a_i \le N$) Plan $i$ builds a bridge from district $i$ to district $-a_i$. The same value may appear more than once.

For each test case, print the number of crossing bridge pairs on its own line.