题目描述

给定 $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$。

数据范围

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

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

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