Segments Removal
Contest: Codeforces Round 452 (Div. 2)
Difficulty rating: 2000
Tags: data structures, dsu, flows, implementation, two pointers

Vasya has an array of integers of length n.

Vasya performs the following operations on the array: on each step he finds the longest segment of consecutive equal integers (the leftmost, if there are several such segments) and removes it. For example, if Vasya's array is [13, 13, 7, 7, 7, 2, 2, 2], then after one operation it becomes [13, 13, 2, 2, 2].

Compute the number of operations Vasya should make until the array becomes empty, i.e. Vasya removes all elements from it.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 200 000) — the length of the array.

The second line contains a sequence a1, a2, ..., an (1 ≤ ai ≤ 109) — Vasya's array.

Output format:
Print the number of operations Vasya should make to remove all elements from the array.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, at first Vasya removes two fives at the second and third positions. The array becomes [2, 2]. In the second operation Vasya removes two twos at the first and second positions. After that the array becomes empty.

In the second example Vasya has to perform five operations to make the array empty. In each of them he removes the first element from the array.

In the third example Vasya needs three operations. In the first operation he removes all integers 4, in the second — all integers 100, in the third — all integers 2.

In the fourth example in the first operation Vasya removes the first two integers 10. After that the array becomes [50, 10, 50, 50]. Then in the second operation Vasya removes the two rightmost integers 50, so that the array becomes [50, 10]. In the third operation he removes the remaining 50, and the array becomes [10] after that. In the last, fourth operation he removes the only remaining 10. The array is empty after that.

Example input:
4
2 5 5 2

Example output:
2

Example input:
5
6 3 4 1 5

Example output:
5

Editorial:
We will use to set of pairs. In the first set (call it len) we will store all segments consisting of the same numbers in a format — the length of the segment multiplied on  - 1 and the position of the beginning of the segment. In the second set (call it segments) we will store all segments consisting of the same numbers in a format — the position of the beginning of the segment and the length of the segment.
Initially we will put in the sets all segments from the given array consisting of the same numbers.
After that we will repeat the following algorithm until in sets there are non-deleted segments:
• increase answer on 1;
• take from lens the longest and the leftmost segment (it will be in the beginning of the lens, because we store here all length multiplied on  - 1) and remove it from lens. Let this segment beginning in the position st and has length len;
• with help of lowerbound we can find in segments the left and the right segments relatively the segment from the previous article. After that we should remove from the segments the segment (st, len);
• if both left and right relatively of the current longest segment there are non-deleted segments and they consisting of the same numbers, we should to unite them in one segment. To do this, we should remove the left and right segments from lens and segments and put the new merged segment in lens and segments in the described format.