4033: 罗dalao与小火车

罗dalao收到了他的粉丝协会送给他的礼物，一套小火车玩具
这套小火车玩具有n节车厢，每节车厢都有一个编号，每节编号唯一且为1到n中的的一个数
这套小火车玩具十分特殊，车厢不能任意拼接，编号为i的车厢可以拼到编号为i-1的车厢后或编号为i+1的车厢前，但是无法和其他编号的车厢拼接
如：编号为3的车厢可以和编号为2和4的车厢拼接成2-3-4
所以拼接好的一段中车厢的编号一定是连续的
罗dalao把这n节车厢摆成了长度为n的一行，然后他发现他把编号顺序弄乱了
他现在想知道对于每个1<=i<=n，在[1,i]这个区间内的所有车厢，最少可以拼接成多少段

第一行一个整数n (1<=n<=1e6)
第二行n个整数用空格隔开，输入保证这n个数为1-n的一个排列

输出一行n个用空格隔开的整数，第i个表示[1,i]这个区间内的所有车厢最少能拼成多少段，输出末尾无空格

6
1 3 4 2 6 5

1 2 2 1 2 1

样例解释:
[1,1]：1
[1,2]：可拼接成 1, 3
[1,3]：可拼接成 1, 3-4
[1,4]：可拼接成 1-2-3-4
[1,5]：可拼接成 1-2-3-4, 6
[1,6]：可拼接成 1-2-3-4-5-6