Codeforces Round 800 (Div. 1) |
---|
Finished |
Yeri has an array of $$$n + 2$$$ non-negative integers : $$$a_0, a_1, ..., a_n, a_{n + 1}$$$.
We know that $$$a_0 = a_{n + 1} = 0$$$.
She wants to make all the elements of $$$a$$$ equal to zero in the minimum number of operations.
In one operation she can do one of the following:
Help her find the minimum number of operations needed to make all elements of $$$a$$$ equal to zero.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).
Print a single integer — the minimum number of operations needed to make all elements of $$$a$$$ equal to zero.
6 1 4 2 4 0 2
7
5 1 3 5 4 2
9
4 0 0 0 0
0
In the first sample, you get $$$\langle 1, \underline{1}, 2, 4, 0, 2 \rangle$$$ by performing the first operation and $$$\langle 1, 4, 2, \underline{2}, 0, 2 \rangle$$$ by performing the second operation.
One way to achieve our goal is shown below. (The underlines show the last change.) $$$\langle 1, 4, 2, 4, 0, 2 \rangle \to \langle 1, 4, 2, \underline{2}, 0, 2 \rangle \to \langle 1, \underline{1}, 2, 2, 0, 2 \rangle \to \langle 1, 1, 2, 2, 0, \underline{0} \rangle \to \langle 1, 1, 2, \underline{0}, 0, 0 \rangle \to \langle 1, 1, \underline{0}, 0, 0, 0 \rangle \to \langle \underline{0}, 1, 0, 0, 0, 0 \rangle \to \langle 0, \underline{0}, 0, 0, 0, 0 \rangle $$$
In the third sample each element is already equal to zero so no operations are needed.
Name |
---|