解题思路
先固定一个位置 i，思考哪些包含 i 的连续子区间 [l…r] 会让 ai 恰好成为该区间的中位数。
关键性质转化
设当前子区间中：
P4711.第3题-中，太中了
题目内容
给定一个长度为 n 的排列 {a1,a2,…,an}，请你统计对于每个位置 i，元素 ai 在多少个不同的连续子区间中恰好是该子区间的中位数。换句话说，对于每个位置 i，统计包含位置 i 的所有连续子区间 [l…r] 中，元素 ai 恰好是该子区间的中位数的个数。
【名词解释】
中位数：对于数组 {b1,b2,…,bx}，将所有元素从小到大排序后，位于第 ⌈2x+1⌉ 个位置的元素即为该数组的中位数。
长度为 n 的排列：由 1,2,…,n 这 n 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如，{2,3,1,5,4} 是一个长度为 5 的排列，而 {1,2,2} 和 {1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T（1≤T≤10），表示数据组数。每组测试数据描述如下：
- 第一行输入一个整数 n（1≤n≤5000），表示数组长度；
- 第二行输入 n 个整数 a1,a2,…,an（1≤ai≤n），表示一个长度为 n 的排列。
除此之外，保证单个测试文件中所有 n 的总和不超过 5000。
输出描述
对于每组测试数据，输出一行，包含 n 个整数。其中，第 i 个整数表示元素 ai 作为中位数的连续子区间个数。
样例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。
