#P17884. troS XEM

troS XEM

对于一个非负整数集合 SS,定义 mex⁡(S)\operatorname{mex}(S) 为不属于 SS 的最小非负整数。

Mayoi 有一个长度为 nn 的非负整数数组 aa。她想让数组按非递减顺序排列。

她可以执行任意多次以下操作,也可以不操作:

  • 选择 ii,满足 1≤i≤∣a∣−21\le i\le |a|-2。
  • 将当前数组中连续的三个元素 ai,ai+1,ai+2a_i,a_{i+1},a_{i+2} 替换成一个元素 mex⁡({ai,ai+1,ai+2})\operatorname{mex}(\{a_i,a_{i+1},a_{i+2}\}),其余元素的相对顺序保持不变。

每次操作后,数组长度减少 22。

求使数组变为非递减序列所需的最少操作次数。如果无法做到,输出 −1-1。

输入格式

第一行一个整数 nn。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出一个整数,表示最少操作次数;如果不存在可行操作方案,则输出 −1-1。

数据范围

2≤n≤5×1052\le n\le5\times10^5,0≤ai≤1090\le a_i\le10^9。

样例 1

3
4 1 3
1

样例 2

2
4 3
-1

样例说明

样例 1 可以把整个数组替换成 [0][0]。

样例 2 的数组长度小于 33,无法执行操作,且原数组不是非递减的。