B. Array

时间限制： 每个测试点 1.5 秒 内存限制： 256 MB

题目描述

给定一个长度为 ( n ) 的整数数组 ( a )。

对于每个下标 ( i )，你需要求出一个最大值：

在所有整数 ( k ) 的取值中，最大化满足以下条件的下标 ( j ) 的数量：

• $( j > i )$
• $( |a_i - k| > |a_j - k| )$

也就是说，你可以自由选择一个整数 ( k )，使得与 ( a_i ) 的距离严格大于与 ( a_j ) 的距离的 ( j ) 的数量尽可能多。

输入格式

每个测试包含多组数据。

• 第一行是整数 $( t )（(1 \le t \le 100)）$，表示测试组数。

• 对于每组测试：

  • 第一行是整数 $( n )（(1 \le n \le 5000)）$。
  • 第二行包含 ( n ) 个整数 $( a_1, a_2, \dots, a_n )（(-10^9 \le a_i \le 10^9)）$。

保证所有测试数据中 ( n ) 的总和不超过 5000。

输出格式

对于每组测试，输出一行 ( n ) 个整数，第 ( i ) 个数表示对应下标 ( i ) 的答案。

样例输入

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 > 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 = 998244353 )），没有满足条件的 ( j )