A104743.长相守·叹别离

题目背景

往岁乘宵醒惊蛰，横刀相守独叩天。

巷中幼孤羽，只身入方圆。

离火弈长生，尘世幸相会。

题目描述

我们称一个整数序列为相守的，当且仅当其满足以下条件：

• 对于除第一个元素外的每个元素，其左侧存在一个比它小的元素；
• 对于除最后一个元素外的每个元素，其右侧存在一个比它大的元素；

例如，$[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$ 的最长相守子序列的长度。

测试点	$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$。