← 返回题目列表

AtCoder · arc221_c

C. 两个双端队列排序

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给你一个正整数 N 和长度-N 正整数序列 A=(A_1,A_2,\dots,A_N).

还有一个长度-0 正整数序列 B.

您可以在以下时间之间执行以下操作 0 和 N 次,含在内。

  • 删除第一个或最后一个元素 A,并将该元素附加到 B.

鉴于以下情况,您可以执行的最大操作数是多少 B 运算后必须是严格递增的序列?

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1\le T\le 3\times 10^5
  • 1\le N\le 3\times 10^5
  • 1\le A_i \le N (1\leq i\leq N)
  • 总和 一个输入文件中的 N 所有测试用例最多 3\times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

按顺序输出测试用例的答案,以换行符分隔。


样本输入 1

3
5
3 1 4 1 5
3
2 2 1
16
3 4 5 7 12 15 1 15 16 8 14 2 16 14 9 2

示例输出 1

4
2
11

对于第一个测试用例,请考虑执行如下操作。

  • 删除第一个元素 A 并将其附加到末尾 B。现在 A=(1,4,1,5),B=(3).
  • 删除第一个元素 A 并将其附加到的开头 B。现在 A=(4,1,5),B=(1,3).
  • 删除第一个元素 A 并将其附加到末尾 B。现在 A=(1,5),B=(1,3,4).
  • 删除最后一个元素 A 并将其附加到末尾 B。现在 A=(1),B=(1,3,4,5).

决赛 B=(1,3,4,5) 是严格递增序列,操作次数为 4。不可能在满足条件的情况下进行五次操作,所以答案是 4.

对于第二个测试用例,请注意 B=(1,2,2) 不是严格递增的序列。