T2 最长上升子序列（lis）

时间限制：$1$ 秒。内存限制：$512$ MB。

题目描述

给定 $1,2,\ldots,n$ 的一个排列 $a$。对每个 $i=1,2,\ldots,n-1$，交换 $a_i$ 与 $a_{i+1}$，求交换后排列的最长严格上升子序列长度。

各次交换相互独立，每次都从原排列开始。

子序列由若干位置按从左到右的顺序选出，位置不必连续；严格上升指选出的数依次增大。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，表示排列 $a$。

输出格式

按交换位置 $i$ 从小到大的顺序，输出 $n-1$ 个答案。

样例

输入：

4
1 3 2 4

输出：

3 4 3

样例解释

交换中间两个数，得到 $(1,2,3,4)$，答案为 $4$。另外两次交换分别得到 $(3,1,2,4)$ 和 $(1,3,4,2)$，最长上升子序列长度都是 $3$。

附加样例 lis2.in/.ans、lis3.in/.ans、lis4.in/.ans 分别满足测试点 $9\sim11$、$12\sim13$、$14\sim20$ 的限制。

数据范围

测试点编号	$n\le$	特殊性质
1—2	$9$	无
3—4	$200$
5—6	$2000$
7—8	$6000$
9—11	$2\times10^5$	$A$
12—13		$B$
14—20		无

对于所有测试点，$2\le n\le2\times10^5$，$a$ 是 $1$ 至 $n$ 的排列。

特殊性质 $A$：原排列的最长严格上升子序列长度不超过 $10$。

特殊性质 $B$：原排列的最长严格上升子序列按所选位置区分时，恰好只有一种。