题目内容

给定一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$。对于每个 $i = 1, 2, \dots, n$，定义前缀 $[1, i]$ 的“值域闭区间”为包含从该前缀元素的最小值到最大值之间所有整数的集合，即闭区间 $[\min(a_1,\dots,a_i), \max(a_1,\dots,a_i)]$。请你求出不属于该闭区间的最小非负整数。

数据规模：序列长度 $n$ 满足 $1 \le n \le 2 \times 10^5$，所有元素 $a_i$ 均为整数且满足 $0 \le a_i \le 10^9$。

输入描述

第一行包含一个整数 $n$，表示序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列中的元素，相邻整数之间用一个空格分隔。