题目描述

称一个数字数组是 $k$ -精致的，如果它至少包含两个元素，并且任意两个相邻的数字之差至少为 $k$。

给定一个长度为 $n$ 的排列 $^{\text{∗}}$ $p$。对于每个 $k$ 从 $1$ 到 $n-1$，求出 $k$ -精致子数组的数量 $^{\text{†}}$。

$^{\text{∗}}$ 一个长度为 $n$ 的排列是一个包含从 $1$ 到 $n$ 的每个整数恰好一次的数组，顺序任意。

$^{\text{†}}$ 一个数组的子数组是指数组中一个或多个连续元素组成的序列。

输入格式

第一行包含整数 $t$（$1 \le t \le 25000$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$，表示排列的长度（$2 \le n \le 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $p_i$，表示排列的元素（$1 \le p_i \le n$）。保证 $p_i$ 互不相同。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出所有 $k$ 从 $1$ 到 $n-1$ 的 $k$ -精致子数组的数量。

样例

3
5
5 1 4 2 3
3
3 2 1
4
3 1 2 4

10 6 3 1 
3 0 
6 2 0

来源

Codeforces 2184E，英文题名 Exquisite Array。