← 返回题目列表

Codeforces · 2184/E

E. 精致阵列

中文机器翻译题面 查看原题

如果一个数字数组至少有两个元素并且任何两个相邻数字相差至少 $$$k$$$,我们称其为 $$$k$$$ 精致数组。

给你一个长度为 $$$n$$$ 的排列$$$^{\text{*}}$$$ $$$p$$$。对于从 $$$1$$$ 到 $$$n - 1$$$ 的每个 $$$k$$$,找到 $$$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 \cdot 10^5$$$。

输出

对于每个测试用例,输出从 $$$1$$$ 到 $$$n - 1$$$ 的所有 $$$k$$$ 的 $$$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