Два отрезка \([l_1, r_1]\) и \([l_2, r_2]\) пересекаются, если существует хотя бы одно число \(x\), такое, что \(l_1 \le x \le r_1\) и \(l_2 \le x \le r_2\).
Массив отрезков \([[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]]\) называется красивым, если \(k\) четно, и его можно разбить на \(\frac{k}{2}\) пар таким образом, что:
- каждый элемент массива принадлежит ровно одной паре;
- отрезки в каждой паре пересекаются между собой;
- отрезки из разных пар не пересекаются.
Например, массив \([[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]\) является красивым, так как его можно разбить на \(3\) пары следующим образом:
- первый элемент массива (отрезок \([2, 4]\)) и третий элемент массива (отрезок \([2, 4]\));
- второй элемент массива (отрезок \([9, 12]\)) и пятый элемент массива (отрезок \([10, 13]\));
- четвертый элемент массива (отрезок \([7, 7]\)) и шестой элемент массива (отрезок \([6, 8]\)).
Как видно, отрезки в каждой паре пересекаются, а отрезки из разных пар не пересекаются.
Дан массив из \(n\) отрезков \([[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]]\). Вам нужно удалить минимально возможное количество элементов из этого массива, чтобы получившийся массив был красивым.
Примечание
В первом наборе входных данных достаточно удалить \(5\)-й элемент массива отрезков. Тогда получится массив \([[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]\), который является красивым.
Во втором наборе входных данных можно удалить \(1\)-й, \(3\)-й и \(4\)-й элементы массива. Тогда получится массив \([[2, 8], [5, 6]]\), который является красивым.
В третьем наборе входных данных необходимо удалить весь массив.