你可能对在数组中寻找最长上升子序列这一经典问题非常熟悉。设 $a$ 是一个由 $n$ 个整数组成的数组。如果子序列 $i_1 < i_2 < \dots < i_k$ 满足 $a_{i_1} < a_{i_2} < \dots < a_{i_k}$，则称其为上升子序列。最长上升子序列是长度最大的上升子序列。当然，我们不会让你去解决这个经典问题；你需要解决它更复杂的版本……

最初，有一个空数组 $a$。然后，数字 $1, 2, \dots, n$ 按此顺序依次被添加到数组中。数字 $i$ 被添加到数组的第 $p_i$ 个位置。数组中的位置用从 $1$ 到 $k$ 的整数编号，其中 $k$ 是数组的当前大小。当在大小为 $k$ 的数组的第 $p$ 个位置添加一个元素时，原本处于位置 $p$ 到 $k$ 的所有元素都会向右移动一个位置，而当前元素会被添加到腾出的空间中。

你的任务是确定每次添加新元素后，数组中最长上升子序列的长度。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$) —— 添加的元素个数。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le i$) —— $p_i$ 表示元素 $i$ 被添加的位置。

输出格式

输出 $n$ 个整数 —— 每次添加新元素后，数组中最长上升子序列的长度。

样例

输入样例 1

5
1 2 1 3 4

输出样例 1

1
2
2
2
3

输入样例 2

1
1

输出样例 2

1

说明

第一个样例中数组的变化过程如下：$[] \to [1] \to [1, 2] \to [3, 1, 2] \to [3, 1, 4, 2] \to [3, 1, 4, 5, 2]$。