题解

题目描述

小美有一个长度为 $n$ 的数组 $a$，数组中所有元素的值不相同，且数组的下标从 $1$ 开始。

她计划对这个数组中的每个元素进行“数数”，首先会从数组中数值最小的元素的索引开始，每次数数时，她会选择下一个值刚好大于当前元素值的位置，直到所有元素都被数过为止。

例如，假设数组 $a = [1,3,5]$，小美一开始选择的是索引 $i=1$ （此时 $a_1=1$），她会接着找到第一个比 $1$ 大的元素 $3$（索引 $i=2$），然后再找到第一个比 $3$ 大的元素 $5$（索引 $i=3$）。整个数数过程为：$a_1 \to a_2 \to a_3$。

题目内容

小美有一个长度为 $n$ 的数组 $a$ ，数组中所有元素的值不相同，且数组的下标从 $1$ 开始。

她计划对这个数组中的每个元素进行“数数”，始会从数组中数值最小的元素的素引开始，每次数数时，她会选将第一个值大于当前位置元素值的元素，直到所有元素都被数过为止。

例如，假设数组 $a=[1,3,5]$ ，小美一开始选择的是索引 $i=2$ (此时 $a_2=1$ )，她会接着找到第一个比 $1$ 大的元素 $3$ (索引 $i=1$ )，然后再找到第一个比 $3$ 大的元素 $5$ (索引 $i=3$ )。整个数数过程为： $a_2→a_1→a_3$。

在这一过程中，如果小美的操作是从较小索引移动到较大索引(即 $j>i$ )，我们称之为正向传送；如果是从较大索引移动到较小索引(即 $j＜i$ )，则称之为逆向传送。

你的任务是帮助小美计算她在整个数数过程中需要进行多少次正向传送和多少次逆向传送。

输入描述

每个测试文件均包含多组测试数。第一行输入一个整数 $T(1≤T≤1000)$ 代表数据组数，每组测试数据描述如下：

第一行一个整数 $n(1≤n≤2×10^5)$ ，表示数组长度。

第二行 $n$ 个整数，第 $i$ 个数为 $a_i(1≤a_i≤10^5)$ ，表示数组元素。

单个测试文件 $∑ n≤2×10^5$

输出描述

共 $T$ 行，每行两个整数，分别表示正向传送和逆向传送的次数，以空格隔开。

样例1

输入

2
3
1 2 3
3
3 2 1

输出

2 0
0 2