分数: 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) 不是严格递增的序列。