#P17869. 队列编辑器 2
队列编辑器 2
M. 队列编辑器 2
一个队列中依次放着排列 ,另有一个初始为空的栈。重复以下操作,直到队列为空:
- 取出队首元素,记为 。
- 只要栈非空且栈顶大于 ,就弹出栈顶并加入队尾;按弹出的先后顺序加入。
- 将 压入栈顶。
可以证明该过程有限步后结束。求整个过程中压栈的总次数。
输入格式
第一行测试组数 。每组先给出 ,再给出 的排列 。
,所有测试的 之和不超过 。
输出格式
每组输出压栈总次数,使用 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