Kendieer 是观察力惊人的大师，他可以从远处观察魔法数组，并看出其中“突出”的数字。 对于一个长度为 的序列 ，若下标 满足以下至少一个条件，则称 是可见的： 从左往右看可以看到它，即对于所有 ，都有 ； 从右往左看可以看到它，即对于所有 ，都有 。 换句话说，如果 左边没有比它大的数，或者右边没有比它大的数，那么 就是可见的。 例如，在序列 中， 是可见的，因为从左往右看可以看到它；而 是不可见的，因为无论从左往右看还是从右往左看，它都会被更大的数挡住。 现在给定一个长度为 的排列 。对于每一个下标 ，请你求出有多少个子区间 ，满足 ，且将该子区间作为一个独立序列时， 是可见的。 【名词解释】 长度为 的排列是由 这 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， 是一个长度为 的排列，而 和 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。 子区间：从原序列中，连续地选择一段元素（可以全选，但不可以不选）得到的新序列。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数。每组测试数据描述如下：第一行输入一个整数 ，表示排列长度。第二行输入 个整数 ，表示排列 。除此之外，保证单个测试文件的 之和不超过 。

输出描述:

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