#P17869. 队列编辑器 2

队列编辑器 2

M. 队列编辑器 2

一个队列中依次放着排列 a1,…,ana_1,\ldots,a_n,另有一个初始为空的栈。重复以下操作,直到队列为空:

  1. 取出队首元素,记为 xx。
  2. 只要栈非空且栈顶大于 xx,就弹出栈顶并加入队尾;按弹出的先后顺序加入。
  3. 将 xx 压入栈顶。

可以证明该过程有限步后结束。求整个过程中压栈的总次数。

输入格式

第一行测试组数 T≥1T\ge1。每组先给出 nn,再给出 1…n1\ldots n 的排列 a1,…,ana_1,\ldots,a_n。

1≤n≤5×1051\le n\le5\times10^5,所有测试的 nn 之和不超过 5×1055\times10^5。

输出格式

每组输出压栈总次数,使用 64 位整数。

样例 1

输入:

4
1
1
3
1 2 3
3
2 1 3
3
3 1 2

输出:

1
3
5
4

样例 2

输入:

2
3
2 3 1
6
1 3 4 6 2 5

输出:

6
15