Vasya 有一个长度为 n 的整数数组。
Vasya 对数组执行以下操作:在每一步中,他都会找到连续相等整数的最长段(如果有多个这样的段,则为最左边)并将其删除。例如,如果Vasya的数组是[13, 13, 7, 7, 7, 2, 2, 2],那么经过一次操作就变成了[13, 13, 2, 2, 2]。
计算 Vasya 应该进行的操作数,直到数组变空,即 Vasya 删除其中的所有元素。
输入
第一行包含一个整数 n (1 ≤ n ≤ 200 000) — 数组的长度。
第二行包含序列 a1, a2, ..., an (1 ≤ ai ≤ 109) — Vasya 的数组。
输出
打印 Vasya 为从数组中删除所有元素而应执行的操作数。
示例
输入 #1
4 2 5 5 2
输出 #1
2
输入 #2
5 6 3 4 1 5
输出 #2
5
输入 #3
8 4 4 4 2 2 100 100 100
输出 #3
3
输入#4
6 10 10 50 10 50 50
输出#4
4
注意
在第一个示例中,首先 Vasya 在第二个和第三个位置删除了两个五。数组变为 [2, 2]。在第二次操作中,Vasya 删除了第一和第二位置的两个双。之后数组变空。
在第二个示例中,Vasya 必须执行五次操作才能使数组为空。在每个例子中,他都会从数组中删除第一个元素。
在第三个示例中,Vasya 需要三个操作。在第一个操作中,他删除了所有整数 4,在第二个操作中,他删除了所有整数 100,在第三个操作中,他删除了所有整数 2。
在第一个操作的第四个示例中,Vasya 删除了前两个整数 10。之后数组变为 [50, 10, 50, 50]。然后在第二个操作中,Vasya 删除了最右边的两个整数 50,使数组变为 [50, 10]。在第三次操作中,他删除了剩余的 50,之后数组变为 [10]。在最后第四次操作中,他删除了仅剩的 10 个。此后数组为空。