{"raw_statement":[{"iden":"statement","content":"Vasya has an array of integers of length _n_.\n\nVasya 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\\].\n\nCompute the number of operations Vasya should make until the array becomes empty, i.e. Vasya removes all elements from it."},{"iden":"input","content":"The first line contains a single integer _n_ (1 ≤ _n_ ≤ 200 000) — the length of the array.\n\nThe second line contains a sequence _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — Vasya's array."},{"iden":"output","content":"Print the number of operations Vasya should make to remove all elements from the array."},{"iden":"examples","content":"Input\n\n4\n2 5 5 2\n\nOutput\n\n2\n\nInput\n\n5\n6 3 4 1 5\n\nOutput\n\n5\n\nInput\n\n8\n4 4 4 2 2 100 100 100\n\nOutput\n\n3\n\nInput\n\n6\n10 10 50 10 50 50\n\nOutput\n\n4"},{"iden":"note","content":"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.\n\nIn 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.\n\nIn 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.\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"Vasya 有一个长度为 $n$ 的整数数组。\n\nVasya 对数组执行以下操作：在每一步中，他找到最长的连续相等整数段（如果有多个这样的段，则选择最左边的），并将其移除。例如，如果 Vasya 的数组是 $[13, 13, 7, 7, 7, 2, 2, 2]$，那么经过一次操作后，它变为 $[13, 13, 2, 2, 2]$。\n\n计算 Vasya 需要进行多少次操作，直到数组变为空，即 Vasya 移除了所有元素。\n\n第一行包含一个整数 $n$（$1 ≤ n ≤ 200 000$）——数组的长度。\n\n第二行包含一个序列 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 10^9$）——Vasya 的数组。\n\n请输出 Vasya 为移除数组中所有元素所需进行的操作次数。\n\n在第一个例子中，首先 Vasya 移除了第二个和第三个位置的两个 5。数组变为 $[2, 2]$。在第二次操作中，Vasya 移除了第一个和第二个位置的两个 2。之后数组变为空。\n\n在第二个例子中，Vasya 需要执行五次操作才能使数组变为空。每次操作他都移除数组的第一个元素。\n\n在第三个例子中，Vasya 需要三次操作。第一次操作中他移除了所有 4，第二次移除了所有 100，第三次移除了所有 2。\n\n在第四个例子中，第一次操作 Vasya 移除了前两个 10。之后数组变为 $[50, 10, 50, 50]$。然后在第二次操作中，Vasya 移除了最右边的两个 50，数组变为 $[50, 10]$。在第三次操作中，他移除了剩余的 50，数组变为 $[10]$。在最后一次（第四次）操作中，他移除了唯一的剩余元素 10。之后数组变为空。"},{"iden":"input","content":"第一行包含一个整数 $n$（$1 ≤ n ≤ 200 000$）——数组的长度。第二行包含一个序列 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 10^9$）——Vasya 的数组。"},{"iden":"output","content":"请输出 Vasya 为移除数组中所有元素所需进行的操作次数。"},{"iden":"examples","content":"输入\n4\n2 5 5 2\n输出\n2\n\n输入\n5\n6 3 4 1 5\n输出\n5\n\n输入\n8\n4 4 4 2 2 100 100 100\n输出\n3\n\n输入\n6\n10 10 50 10 50 50\n输出\n4"},{"iden":"note","content":"在第一个例子中，首先 Vasya 移除了第二个和第三个位置的两个 5。数组变为 $[2, 2]$。在第二次操作中，Vasya 移除了第一个和第二个位置的两个 2。之后数组变为空。\n\n在第二个例子中，Vasya 需要执行五次操作才能使数组变为空。每次操作他都移除数组的第一个元素。\n\n在第三个例子中，Vasya 需要三次操作。第一次操作中他移除了所有 4，第二次移除了所有 100，第三次移除了所有 2。\n\n在第四个例子中，第一次操作 Vasya 移除了前两个 10。之后数组变为 $[50, 10, 50, 50]$。然后在第二次操作中，Vasya 移除了最右边的两个 50，数组变为 $[50, 10]$。在第三次操作中，他移除了剩余的 50，数组变为 $[10]$。在最后一次（第四次）操作中，他移除了唯一的剩余元素 10。之后数组变为空。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ a_i \\in \\mathbb{Z}^+ $.  \n\nDefine a *run* as a maximal consecutive subsequence of equal elements.  \nLet $ R = (r_1, r_2, \\dots, r_m) $ be the sequence of runs of $ A $, where each $ r_j = (v_j, \\ell_j) $, with $ v_j $ the value and $ \\ell_j \\geq 1 $ the length of the $ j $-th run, and $ \\sum_{j=1}^m \\ell_j = n $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200{,}000 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nCompute the number of operations required to empty the array, where each operation:  \n- Identifies the leftmost longest run (i.e., the run with maximum $ \\ell_j $, breaking ties by leftmost position),  \n- Removes that entire run,  \n- Concatenates the remaining runs.  \n\nThe process repeats until the array is empty.  \n\nLet $ f(R) $ denote the number of operations needed to empty the array starting from run sequence $ R $.  \nThen, the objective is to compute $ f(R) $.","simple_statement":null,"has_page_source":false}