No.921 Zunda Arrow
polylogK
lumc_If you are experiencing a problem where math formulas are not displayed, please take the following measures.
https://twitter.com/yukicoder/status/1191757446596812800?s=20
Problem Statement
$N$ mochi are lined up in a row, and the mochi at the $i$-th position from the left has size $A_i$.
Zunko can use the Zunda Arrow any number of times to turn a mochi into a zunda mochi.
A zunda mochi does nothing when it is adjacent to a mochi, but when it is adjacent to another zunda mochi, the following changes occur.
- If the adjacent zunda mochi have the same size, nothing changes.
- If the adjacent zunda mochi have different sizes, the smaller zunda mochi disappears (the larger zunda mochi does not change).
When Zunko chooses well which mochi to turn into zunda mochi, find the maximum number of zunda mochi that can remain in the end.
Input
$N$
$A_1\ A_2\ \cdots\ A_{N - 1}\ A_N$
- $1 \le N \le 10^5$
- $1 \le A_i \le 10^5$
- All inputs are integers.
Output
Print the maximum number of zunda mochi that can remain in the end, as an integer on one line.
Sample
Sample 1
Input
5 1 2 3 4 5
Output
3
This can be achieved by turning the 1st, 3rd, and 5th mochi from the left into zunda mochi.
Sample 2
Input
9 1 2 2 2 1 3 2 2 2
Output
6
This can be achieved by turning all the mochi of size 2 into zunda mochi.
Note that zunda mochi of the same size do not absorb each other.
Sample 3
Input
8 7 1 6 8 9 4 3 2
Output
4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。