题目描述

薯条哥有$n$个整数$[a_1,a_2,...,a_n]$，他定义区间$[l,r]$的“数字凸包区间”为

$[min\left \{a_l,...,a_r \right \} ,max\left \{a_l,...,a_r \right \} ]$。

现在，对于每一个$i= 1,2,...,n$，直接输出不属于$[1,i]$这个区间的“数字凸包区间”的最小非负整数。

输入描述

第一行输入一个整数$n(1\le n\le 2\times 10^5)$代表整数数量询问次数。

第二行输入$n$个整数$a_1,a_2,...,a_n(0\le a_i\le 10^9)$代表元素

输出描述

在一行上输出$n$个整数，代表对于每一个$i$的答案。

样例1

输入

5
1 0 4 5 1

输出

0 2 5 6 6

样例解释

对于第一次询问，“数字凸包区间”为$[1,1]$，不属于这个“数字凸包区间”的最小非负整数为$0$。

对于第二次询问，“数字凸包区间”为$[0,1]$，不属于这个“数字凸包区间”的最小非负整数为$2$。