← 返回比赛

已结束 KTXY Round 1

← 上一题下一题 →

A7217 | $长相守\cdot叹别离$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

题目背景 往岁乘宵醒惊蛰，横刀相守独叩天。 > 巷中幼孤羽，只身入方圆。 > 离火弈长生，尘世幸相会。 题目描述 我们称一个整数序列为相守的，当且仅当其满足以下条件： - 对于除第一个元素外的每个元素，其左侧存在一个比它小的元素； - 对于除最后一个元素外的每个元素，其右侧存在一个比它大的元素； 例如，$[1, 2]$、$[42]$、$[1, 4, 2, 4, 7]$ 和 $[1, 2, 4, 8]$ 是相守的，但 $[2, 2, 4]$ 和 $[1, 3, 5, 3]$ 不是。 注意：子序列是指通过删除原序列中某些元素（可能为零个）而不改变剩余元素顺序得到的新序列。 长离给定了你一个长度为 $n$ 的整数数组 $a$。请找出数组 $a$ 的最长相守子序列，并输出其长度。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）——数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）——数组 $a$。

输出格式

输出一个整数——数组 $a$ 的最长相守子序列的长度。

输入输出样例

输入 #1

6
2 3 1 1 2 4

输出 #1

输入 #2

7
1 1 3 4 2 3 4

输出 #2

测试点$n \leq$特殊性质$1$$10$无$2$$300$无$3$$10^3$无$4$$10^4$有$5$$10^4$无$6 \sim 7$$5 \times 10^5$有$8 \sim 10$$5 \times 10^5$无 特殊性质：$\exists i\in[1,n]$ 使得 $a_1 \le a_2 \le \cdots \le a_i$，且 $a_i \ge a_{i+1} \ge \cdots \ge a_{n}$。 对于 $100\%$ 的数据, $1 \leq n \leq 5\times 10^{5} ,1\le a_i \le 10^6$。

C++ 编辑器

输入

输出