#P17884. troS XEM
troS XEM
对于一个非负整数集合 ,定义 为不属于 的最小非负整数。
Mayoi 有一个长度为 的非负整数数组 。她想让数组按非递减顺序排列。
她可以执行任意多次以下操作,也可以不操作:
- 选择 ,满足 。
- 将当前数组中连续的三个元素 替换成一个元素 ,其余元素的相对顺序保持不变。
每次操作后,数组长度减少 。
求使数组变为非递减序列所需的最少操作次数。如果无法做到,输出 。
输入格式
第一行一个整数 。
第二行 个整数 。
输出格式
输出一个整数,表示最少操作次数;如果不存在可行操作方案,则输出 。
数据范围
,。
样例 1
3
4 1 3
1
样例 2
2
4 3
-1
样例说明
样例 1 可以把整个数组替换成 。
样例 2 的数组长度小于 ,无法执行操作,且原数组不是非递减的。