如果一个数字数组至少有两个元素并且任何两个相邻数字相差至少 $$$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$$$ 精致子数组的数量。
示例
输入复制
355 1 4 2 333 2 143 1 2 4
输出复制
10 6 3 13 06 2 0