题目描述

给定一个长为 $n$ 的数组 $\{a_i\}$。

设 $1 \le p \le n$，对于前缀 $[a_1, a_2, \ldots, a_p]$，我们称一个正整数 $x$ 是合法的，当且仅当存在 $1 \le i < j \le p$ 使得 $(a_i,a_j,x)$ 可以拼成一个未退化的三角形。

对于 $p=2,3,\ldots,n$，分别求出合法的 $x$ 的个数。

输入格式

第一行一个正整数 $T$，表示询问组数。

接下来 $T$ 组询问：

每组询问第一行一个整数 $n$，代表序列的长度。

接下来一行 $n$ 个整数，第 $i$ 个整数代表 $a_i$。

输出格式

共 $T$ 行，每行 $n-1$ 个整数，第 $i$ 个数代表前缀 $[a_1, a_2, \ldots, a_{i+1}]$ 的答案。

3
3
114 51 4
3
19 198 10
6
3 1 4 5 9 2

101 108
37 56
1 5 7 12 12

数据范围

对于 $30\%$ 的数据，$T \le 5$，$1 \le n \le 500$； 对于另外 $30\%$ 的数据，$1 \le a_i \le 2 \cdot 10^5$； 对于 $100\%$ 的数据，$1 \le T \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$1 \le \sum n \le 2 \cdot 10^5$，$1 \le a_i < 10^9$，保证所有的 $a_i$ 互不相同。