Background

Original link: https://oier.team/problems/J2B.

Problem Description

You are given a sequence $a_1, a_2, \ldots, a_n$. You can perform some operations on this sequence.

Suppose that before an operation, the sequence length is $m$. In this operation, you may choose an integer $i$ such that $1 \le i \le m - 1$ and $a_i \ne a_{i + 1}$, delete $a_{i + 1}$, and set the value of $a_i$ to any integer.

Find the maximum number of operations you can perform.

Input Format

The first line contains a positive integer $n$, indicating the initial length of the sequence.

The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$.

Output Format

Output a single non-negative integer in one line, indicating the maximum number of operations.

2
1 2

1

3
1 1 1

0

4
1 1 45 14

3

Hint

Sample Explanation #1

You can choose $i = 1$. After deleting $a_2$, set $a_1$ to $3$. Now $a = [3]$, and no more operations can be performed. Therefore, the answer is $1$.

Sample Explanation #2

No operation can be performed, so the answer is $0$.

Constraints

This problem uses bundled testdata and subtask dependencies are enabled.

For all testdata, $1 \le n \le 10^5$ and $1 \le a_i \le 10^9$.

Translated by ChatGPT 5