解题思路

先固定一个位置 $i$，思考哪些包含 $i$ 的连续子区间 $[l\dots r]$ 会让 $a_i$ 恰好成为该区间的中位数。

关键性质转化

设当前子区间中：

• 比 $a_i$ 小的数有 $x$ 个；

题目内容

给定一个长度为 $n$ 的排列 $\{a_1,a_2,\dots,a_n\}$，请你统计对于每个位置 $i$，元素 $a_i$ 在多少个不同的连续子区间中恰好是该子区间的中位数。换句话说，对于每个位置 $i$，统计包含位置 $i$ 的所有连续子区间 $[l\dots r]$ 中，元素 $a_i$ 恰好是该子区间的中位数的个数。

【名词解释】 中位数：对于数组 $\{b_1,b_2,\dots,b_x\}$，将所有元素从小到大排序后，位于第 $\left\lceil\frac{x+1}{2}\right\rceil$ 个位置的元素即为该数组的中位数。 长度为 $n$ 的排列：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如，$\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 10$），表示数据组数。每组测试数据描述如下：

• 第一行输入一个整数 $n$（$1 \le n \le 5000$），表示数组长度；
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le n$），表示一个长度为 $n$ 的排列。

除此之外，保证单个测试文件中所有 $n$ 的总和不超过 $5000$。

输出描述

对于每组测试数据，输出一行，包含 $n$ 个整数。其中，第 $i$ 个整数表示元素 $a_i$ 作为中位数的连续子区间个数。

样例1

输入

2
3
1 2 3
3
2 1 3

输出

1 3 2
3 1 2

说明 在第一个样例中，数组 $\{1,2,3\}$：

• 当 $i = 1$ 时，只有子区间 $\{1\}$ 的中位数为 $1$；
• 当 $i = 2$ 时，子区间 $\{2\},\{1,2\},\{1,2,3\}$ 的中位数均为 $2$；
• 当 $i = 3$ 时，子区间 $\{2,3\},\{3\}$ 的中位数为 $3$。