C. 双端队列排序

AtCoder Regular Contest++ 221

双端队列排序

Two Deques Sorting

AtCoder

⌀ 2899

原题

← BD →

双端队列排序AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

You are given a positive integer $N$ and a length- $N$ sequence of positive integers $A=(A_1,A_2,\dots,A_N)$ .

给定一个正整数 $N$ 和一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$ 。AI (CI翻译)

There is also a length- $0$ sequence of positive integers $B$ .

此外，还有一个长度为 $0$ 的正整数序列 $B$ 。AI (CI翻译)

You can perform the following operation between $0$ and $N$ times, inclusive.

你可以执行以下操作 $0$ 次至 $N$ 次（包括 $0$ 次和 $N$ 次）。AI (CI翻译)

Remove the first or last element of $A$ , and append that element to the beginning or end of $B$ .

从 $A$ 中移除第一个或最后一个元素，并将该元素添加到 $B$ 的开头或末尾。

AI (CI翻译)

What is the maximum number of operations you can perform, given that $B$ must be a strictly increasing sequence after the operations?

在操作结束后，要求 $B$ 必须是严格递增序列。在此条件下，你最多可以执行多少次操作？AI (CI翻译)

You are given $T$ test cases; solve each of them.

给定 $T$ 个测试用例，请分别求出每个测试用例的答案。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$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)$
The sum of $N$ over all test cases is at most $3\times 10^5$ .
All input values are integers.

$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$ 。
所有输入值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入中以以下格式给出：AI (CI翻译)

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

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

AI (CI翻译)

Each test case is given in the following format:

每个测试用例的输入格式如下：AI (CI翻译)

N
A_1 A_2 \ldots A_N

N
A_1 A_2 \ldots A_N

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answers for the test cases in order, separated by newlines.

按顺序输出各个测试用例的答案，每个答案占一行。AI (CI翻译)

样例

Input #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

Output #1

4
2
11

For the first test case, consider performing the operations as follows. - Remove the first element of $A$ and append it to the end of $B$. Now $A=(1,4,1,5),B=(3)$. - Remove the first element of $A$ and append it to the beginning of $B$. Now $A=(4,1,5),B=(1,3)$. - Remove the first element of $A$ and append it to the end of $B$. Now $A=(1,5),B=(1,3,4)$. - Remove the last element of $A$ and append it to the end of $B$. Now $A=(1),B=(1,3,4,5)$. The final $B=(1,3,4,5)$ is a strictly increasing sequence, and the number of operations is $4$. It is impossible to perform five operations while satisfying the condition, so the answer is $4$. For the second test case, note that $B=(1,2,2)$ is not a strictly increasing sequence.

题目信息

题号

arc221_c

所属比赛

AtCoder Regular Contest++ 221

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。