题目内容

米小游有$n$个整数{$a_1,a_2,...,a_n$}，他定义区间$[l,r]$的“数字凸包区间”为 [$min${$a_l,...,a_r$},$max${$a_l,...,a_r$}]。

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

题解

题面描述

给定一个整数 $n$ 和一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$。定义任意区间 $[l,r]$ 的数字凸包区间为

对于每个前缀 $[1,i]$（$i=1,2,\dots,n$），求该前缀构成的数字凸包区间中不属于该区间的最小非负整数。

例如：

• 当 $i=1$ 时，区间为 $[\min\{a_1\},\max\{a_1\}]=[a_1,a_1]$，如果 $a_1\neq 0$ 则 $0$ 不在该区间，答案为 $0$；