ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 C: 学数数导致的

内存限制：524 MB 时间限制：4 S
题面：传统 评测方式：文本比较 上传者：
提交：3 通过：2
返回比赛提交提交记录

题目描述

给出数列 a1,…,an，问有多少个正整数数对 (p,q)(p,q) 使得数列中存在子序列 p,0,p,q。

输入格式

输入包含多组测试数据。 第一行有一个正整数 T(1≤T≤20)表示测试数据组数。

对于每组数据输入两行：

第一行有一个正整数 n(4≤n≤106)，表示数列元素个数。

第二行有 nn 个自然数 a1,a2,…,an(0≤ai≤106)，表示这个数列。

保证数据中只有 1010 组 n>105的数据。

输出格式

对于每组数据，输出一行一个自然数，表示符合题意的数对对数。

输入样例 复制 

2
8
1 2 0 1 0 3 2 2
4
2 0 2 5

输出样例 复制 

3
1

数据范围与提示

$n,q \le 10^5,1 \le x \le n,0 \le y<10^9+7$ It is guaranteed that all operations are chosen independently and randomly from all valid operations with equal probability and there are at most $10$ test cases.