CF2209B Array

You are given an integer array $ a $ of length $ n $ . For each index $ i $ , find the maximum number of indices $ j $ such that $ j \gt i $ and $ |a_i - k| \gt |a_j - k| $ , over all possible integer values of $ k $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 5000 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^9 \le a_i \le 10^9 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ .

For each test case, output $ n $ integers denoting the answer.

In the second test, the answers are: - For $ i=1 $ , you can choose $ k=-195 $ , then $ j=2 $ . - For $ i=2 $ , you can choose $ k=5 $ , there exists no index $ j \gt i $ . In the third test, the answers are: - For $ i=1 $ , you can choose $ k=195 $ , then $ j=2,3,4,5 $ . - For $ i=2 $ , you can choose $ k=78 $ , then $ j=3,4 $ . - For $ i=3 $ , you can choose $ k=15 $ , then $ j=4,5 $ . - For $ i=4 $ , you can choose $ k=15 $ , then $ j=5 $ . - For $ i=5 $ , you can choose $ k=998\,244\,353 $ , there exists no index $ j \gt i $ .