유리 다리

수질 오염은 세계 여러 대도시가 함께 겪는 문제이고, ICPC 나라의 ACM 대도시도 예외가 아니다. 많은 도시가 하수를 처리한 뒤 수원으로 내보내 이 문제를 해결하지만, ACM 대도시는 빈 땅이 모자라서 그 방법을 쓸 수 없다.

그래서 ACM 대도시 정부는 화학적인 방법을 골랐다. 도시 주변 강에 정화 약품을 풀어 물을 정화하는 방식이다. 이 화학 반응에는 햇빛이 필요해서, 강을 건너는 다리를 모두 유리 다리로 바꾸고 있다.

유리 다리도 햇빛의 50%를 막는다. 유리 다리 두 개가 겹친 곳은 전체 햇빛의 25%만 통과시킨다. 약품이 작동하려면 전체 햇빛의 40% 이상이 필요하므로 이 겹침이 문제가 된다. 겹침을 아예 없앨 수는 없어서, 정부는 햇빛이 40%에 못 미치는 구간을 최대한 줄이려고 한다.

정부는 강 하나 위에 다리 $N$개를 새로 놓을 계획이다. 3층 다리는 지을 수 없으므로 한 지점에서 겹치는 다리는 많아야 두 개다. 정부는 다리 두 개가 겹치는 지점이 몇 곳인지 알고 싶다.

강 양쪽 구역은 서로 마주 보게 배치되어 있다. 1번 구역 맞은편이 $-1$번 구역, 2번 구역 맞은편이 $-2$번 구역, 이런 식이다. $i$번째 계획은 $i$번 구역과 $-a_i$번 구역을 잇는 다리다. 다리 $i$와 다리 $j$는 $i < j$이면서 $a_i > a_j$일 때 강 위에서 교차한다. 교차하는 다리 쌍의 개수를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \le T \le 20$)

각 테스트 케이스의 첫 줄에는 새로 놓을 다리의 수 $N$이 주어진다. ($2 \le N \le 100\,000$)

다음 줄에는 정수 $a_1\ a_2\ \dots\ a_N$이 공백으로 구분되어 주어진다. ($1 \le a_i \le N$) 이는 $i$번 구역에서 $-a_i$번 구역으로 다리를 놓는다는 뜻이다. 같은 값이 여러 번 나올 수 있다.

각 테스트 케이스마다 서로 교차하는 다리 쌍의 개수를 한 줄에 출력한다.