33OJ
登录 注册

#P17774. 安达樱不是罪过

安达樱不是罪过

背景

『我!讨厌岛村在我不知道的地方露出笑容!』

题目描述

给定一个长度为 nn 的序列 aa。

有 22 种操作类型:

  1. 选择一个 ii。记 x=MEX⁡([a1,a2,…,ai])x = \operatorname{MEX}([a_1,a_2,\dots,a_i])。对 1≤j≤i1 \le j \le i 执行 aj=min⁡(aj,x)a_j = \min(a_j, x)。
  2. 选择一个 ii。记 x=MEX⁡([ai,ai+1,…,an])x = \operatorname{MEX}([a_i,a_{i+1},\dots,a_n])。对 i≤j≤ni \le j \le n 执行 aj=max⁡(aj,x)a_j = \max(a_j, x)。

问最少操作多少次就可以让 aia_i 全部相同。

注:MEX(S)\text{MEX}(S) 为最小自然数 xx 的值,使得 x∉Sx \notin S。

输入格式

第一行一个整数 nn。

第二行 nn 个整数 a1∼na_{1\sim n}。

输出格式

一行一个整数,表示答案。

9
1 0 1 9 1 0 1 9 1
2

提示

你,去祭典了吧,和我不认识的女孩一起。

我希望你……眼里只有我。

保证 1≤n≤105,0≤ai≤n1 \le n \le 10^5,0 \le a_i \le n。