在阿拉木图附近的一片森林里，有 $N$ 棵树排成一行，从左到右编号为 $1$ 到 $N$。第 $i$ 棵树的高度为 $H_i$。

在一次跳跃中，如果树 $i$ 和树 $j$ ($i < j$) 之间的所有树的高度要么都严格低于树 $i$ 和树 $j$，要么都严格高于树 $i$ 和树 $j$，那么泰山（Tarzan）就可以从树 $i$ 的顶部跳到树 $j$ 的顶部。特别地，他总是可以从树 $i$ 跳到树 $i+1$。更正式地说，当且仅当满足以下至少一个条件时，跳跃是可能的：

• $j = i + 1$
• 对于所有 $k$ ($i < k < j$)：$H_i > H_k$ 且 $H_j > H_k$
• 对于所有 $k$ ($i < k < j$)：$H_i < H_k$ 且 $H_j < H_k$

泰山目前站在第 $1$ 棵树上，他想到达第 $N$ 棵树。泰山的 ICPC 队友阿拜（Abay）可以帮助他。具体来说，阿拜可以执行任意次数的以下操作：选择一个编号 $i$ ($1 \le i \le N$) 和一个整数 $x$ ($0 \le x \le 10^{18}$)，并将 $H_i$ 修改为 $x$。

对于每个 $k$ ($1 \le k \le N$)，求出阿拜最少需要执行多少次修改，才能使泰山在不超过 $k$ 次跳跃内到达第 $N$ 棵树。

输入格式

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

每个测试用例的第一行包含一个整数 $N$（$2 \le N \le 300\,000$），表示树的数量。

每个测试用例的第二行包含 $N$ 个整数 $H_1, H_2, \dots, H_N$（$1 \le H_i \le 10^9$）。

保证所有测试用例的 $N$ 之和不超过 $300\,000$。

输出格式

对于每个测试用例，输出 $N$ 个整数：对于每个 $k$ 从 $1$ 到 $N$，输出阿拜为了让泰山在不超过 $k$ 次跳跃内从第 $1$ 棵树到达第 $N$ 棵树所需执行的最少修改次数。

样例

输入 1

2
3
2 2 4
2
1 1

输出 1

1 0 0
0 0

说明

在第一个测试用例中，对于 $k=1$，阿拜可以将第 $1$ 棵树的高度修改为 $3$，这样泰山就能跳到最后一棵树。对于 $k=2$ 和 $k=3$，泰山无需任何修改即可到达最后一棵树。