← 返回题目列表

Codeforces · 2209/B

B. 数组

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

给你一个长度为$$$n$$$的整数数组$$$a$$$。

对于每个索引 $$$i$$$,查找 最大数量 索引 $$$j$$$ 使得 $$$j \gt i$$$ 和 $$$|a_i - k| \gt |a_j - k|$$$,$$$k$$$ 的所有可能整数值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数表示答案。

示例

输入
复制

6
1
1092
2
105 -105
5
1 2 93 84 2
7
2 9 38 4 7 1 6
10
1 9 20 9 829 3 87 1 283 7
11
9 18 29817 283 3 3928 5726 1942 1000000000 -1000000000 19

输出
复制

0
1 0
4 2 2 1 0
5 4 4 2 2 1 0
8 4 4 3 5 3 2 2 1 0
8 7 7 4 5 3 3 2 2 1 0

注意

在第二次测试中,答案是:

  • 对于 $$$i=1$$$,您可以选择 $$$k=-195$$$,然后选择 $$$j=2$$$。
  • 对于$$$i=2$$$,可以选择$$$k=5$$$,不存在索引$$$j \gt i$$$。

在第三次测试中,答案是:

  • 对于$$$i=1$$$,您可以选择$$$k=195$$$,然后$$$j=2,3,4,5$$$。
  • 对于 $$$i=2$$$,您可以选择 $$$k=78$$$,然后选择 $$$j=3,4$$$。
  • 对于$$$i=3$$$,您可以选择$$$k=15$$$,然后$$$j=4,5$$$。
  • 对于 $$$i=4$$$,您可以选择 $$$k=15$$$,然后选择 $$$j=5$$$。
  • 对于$$$i=5$$$,可以选择$$$k=998\,244\,353$$$,不存在索引$$$j \gt i$$$。