Задача №114965. Направленные точки
Недавно Стёпе подарили набор игры «Направленные точки». Комплект игры состоит из \(n\) направленных точек. Точка с номером \(i\) имеет направление \(t_i\). Если \(t_i = 1\), то точка направлена влево, а если \(t_i = 2\), то точка направлена вправо.
Правила игры очень простые:
- Точку \(i\), направленную влево, можно соединить с какой-то точкой \(j\), меньшей по номеру (\(j < i\)), или вовсе не соединять с другими точками.
- Точку \(i\), направленную вправо, можно соединить с какой-то точкой \(j\), большей по номеру (\(j > i\)), или вовсе не соединять с другими точками.
- В конце игры все соединенные точки объединяются в одну. Например если точка \(1\) соединена с точкой \(2\), а точка \(2\) соединена с точкой \(3\), то в конце игры все три точки объединятся в одну.
Обратите внимание, что если точка \(i\) была соединена с точкой \(j\), то точка \(j\) могла быть соединена с другой точкой.
Цель игры — получить как можно меньше точек в конце игры.
Стёпа пока что только в 1 классе, поэтому просит вас сыграть в эту игру за него и сказать ему минимальное количество точек, которое можно получить в конце игры.
Первая строка содержит одно целое число \(n\) (\(1 \le n \le 100\,000\)) — количество точек в игре.
Вторая строка содержит \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(t_i=1\) или \(t_i=2\)) — направления точек. Если \(t_i = 1\), то точка \(i\) направлена влево, а если \(t_i = 2\), то точка \(i\) направлена вправо.
В единственной строке выведите одно число — минимальное количество точек, которое можно получить в конце игры.
В первом тестовом примере можно соединить точки таким образом:
- \(1\rightarrow5\)
- \(2\rightarrow3\)
- \(3\rightarrow1\)
- \(4\rightarrow3\)
- \(5\) не соединяем
При таком соединении в конце игры останется ровно \(1\) точка.
Во втором тестовом примере можно соединить точки таким образом:
- \(1\) не соединяем
- \(2\rightarrow1\)
- \(3\rightarrow4\)
- \(4\) не соединяем
При таком соединении в конце игры останется ровно \(2\) точки. Можно показать, что ответ меньше не достигается.
Тесты к этой задаче состоят из 4 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.
| Группа | Баллы | Доп. ограничения | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 21 | \(n = 2\) | – | |
| 2 | 27 | \(n = 3\) | – | |
| 3 | 23 | – | – | \(t_{i-1} \le t_i\), при \(i \ge 2\) |
| 4 | 29 | – | 0 – 3 |
5 2 2 1 1 2
1
4 1 1 2 2
2