出题需要魔法

题号：NC317306
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ Kendieer 是观察力惊人的大师，他可以从远处观察魔法数组，并看出其中“突出”的数字。

$\hspace{15pt}$ 对于一个长度为 $k$ 的序列 $a_1,a_2,\dots,a_k$ ，若下标 $i$ 满足以下至少一个条件，则称 $a_i$ 是可见的：
$\hspace{23pt}\bullet\,$ 从左往右看可以看到它，即对于所有 $1\leqslant j<i$ ，都有 $a_j\leqslant a_i$ ；
$\hspace{23pt}\bullet\,$ 从右往左看可以看到它，即对于所有 $i<j\leqslant k$ ，都有 $a_j\leqslant a_i$ 。
$\hspace{15pt}$ 换句话说，如果 $a_i$ 左边没有比它大的数，或者右边没有比它大的数，那么 $a_i$ 就是可见的。
$\hspace{15pt}$ 例如，在序列 $[1,2,5,3,4]$ 中， $1$ 是可见的，因为从左往右看可以看到它；而 $3$ 是不可见的，因为无论从左往右看还是从右往左看，它都会被更大的数挡住。

$\hspace{15pt}$ 现在给定一个长度为 $n$ 的排列 $^\texttt{[1]}$ $p$ 。对于每一个下标 $x$ ，请你求出有多少个子区间 $^\texttt{[2]}$ $[l,r]$ ，满足 $l\leqslant x\leqslant r$ ，且将该子区间作为一个独立序列时， $p_x$ 是可见的。

【名词解释】
$\hspace{15pt}$ 长度为 $n$ 的排列 $^\texttt{[1]}$ 是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
$\hspace{15pt}$ 子区间 $^\texttt{[2]}$ ：从原序列中，连续地选择一段元素（可以全选，但不可以不选）得到的新序列。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数。每组测试数据描述如下：

第一行输入一个整数 ，表示排列长度。
第二行输入  个整数 ，表示排列 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出  个非负整数，第  个整数表示下标为  的元素是可见的子区间数量。

示例1

输入

复制

7
3
2 1 3
5
2 4 5 3 1
6
1 4 2 5 3 6
6
1 2 3 4 5 6
7
1 7 5 2 4 6 3
7
1 2 3 4 7 6 5
12
2 8 5 4 7 12 1 3 6 10 9 11

输出

复制

3 3 3
5 8 9 8 5
6 10 6 12 6 6
6 10 12 12 10 6
7 12 11 7 9 12 7
7 12 15 16 15 12 7
12 22 14 12 26 42 12 16 18 24 12 12