У Yeri есть массив из $$$n + 2$$$ неотрицательных целых чисел: $$$a_0, a_1, ..., a_n, a_{n + 1}$$$.
Мы знаем, что $$$a_0 = a_{n + 1} = 0$$$.
Она хочет сделать все элементы $$$a$$$ равными нулю за минимальное количество операций.
За одну операцию она может сделать одно из следующих действий:
Помогите ей найти минимальное количество операций, необходимых для того, чтобы все элементы $$$a$$$ стали равны нулю.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).
Выведите одно целое число — минимальное количество операций, необходимых для того, чтобы все элементы $$$a$$$ стали равны нулю.
6 1 4 2 4 0 2
7
5 1 3 5 4 2
9
4 0 0 0 0
0
В первом примере вы получите $$$\langle 1, \underline{1}, 2, 4, 0, 2 \rangle$$$ при выполнении первой операции и $$$\langle 1, 4, 2, \underline{2}, 0, 2 \rangle$$$ при выполнении второй операции.
Один из способов достижения нашей цели показан ниже. (Подчеркивания показывают последнее изменение). $$$\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 $$$
В третьем примере каждый элемент уже равен нулю, поэтому никаких операций не требуется.
| Codeforces Round 800 (Div. 1) |
|---|
| Закончено |
