题目描述

小明拿到了一个长度为 $n$ 的正整数序列 $a_1, a_2, \ldots, a_n$。

他可以对这个序列执行若干次操作。每次操作的规则如下：设操作前序列长度为 $m$，选择一个整数 $i$（$1 \le i \le m - 1$），且满足 $a_i \ne a_{i + 1}$，然后删除 $a_{i + 1}$，并将 $a_i$ 修改为任意整数。

求最多能执行多少次操作。

输入格式

第一行包含一个正整数 $n$，表示序列的初始长度。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。

输出格式

一行一个非负整数，表示最多能进行的操作次数。

样例

2
1 2

1

3
1 1 1

0

4
1 1 45 14

3

提示

【样例解释 #1】

选择 $i = 1$，此时 $a_1 = 1 \ne a_2 = 2$，删除 $a_2$ 并将 $a_1$ 设为 $3$。序列变为 $[3]$，无法继续操作。答案为 $1$。

【样例解释 #2】

序列所有元素均为 $1$，不存在相邻不同元素，无法进行任何操作。答案为 $0$。

【数据范围】

本题采用捆绑测试且开启子任务依赖。

对于所有数据，满足 $1 \le n \le 10^5$，$1 \le a_i \le 10^9$。