| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 9 | 6 | 2 | 100.000% |
И когда он снял вторую печать, я слышал второе животное, говорящее: иди и смотри.
И вышел другой конь, рыжий;
и сидящему на нем дано взять мир с земли, и чтобы убивали друг друга;
и дан ему большой меч.
Откровение Иоанна Богослова
Мир перенаселён. Ресурсы планеты на исходе. Жители всех стран на грани отчаяния. Политическая обстановка накаляется с каждым днём. У государств нет ни сил, ни ресурсов на войну друг с другом. В любой момент в любой стране может вспыхнуть кровопролитная гражданская война. Миллионы жертв неизбежны. В результате прошлых войн многие государства оказались разделены географически, образовались анклавы.
Представим карту мира как прямую, на которой расположены города, принадлежащие разным странам. Если на этой прямой подряд находятся несколько городов, принадлежащих одной стране, то все эти города считаются отдельным анклавом этой страны. Если в каком-то анклаве какой-то страны начинается гражданская война, то этот анклав мгновенно слабеет, после чего его целиком захватывает один из соседних с ним анклавов. Если оба соседних анклава принадлежат одной и той же стране, то они объединяются в один анклав.
Второй всадник Апокалипсиса Война, видя приближение конца света, хочет закончить всё это побыстрее. Он может инкогнито внедрить провокатора в любой анклав любой страны и начать там гражданскую войну, что приведет к исчезновению этого анклава с карты мира. Выясните, за сколько внедрений Война сможет оставить в мире ровно один анклав и начать в нем гражданскую войну.
В первой строке задано единственное число $n$ (1ドル \le n \le 500$) --- количество стран на карте мира. Во второй строке задана сама карта мира: номера стран $a_i,ドル которым принадлежат соответствующие города на прямой. Все номера стран являются натуральными числами, не превосходящими 10ドル^9$.
Выведите искомое минимальное число внедрений.
4 1 2 3 1
3
3 1 1 1
1
4 1 2 2 1
2