Предположим, вы играете в игру, где игровое поле выглядит как полоска из \(1 \times 10^9\) квадратных ячеек, пронумерованных от \(1\) до \(10^9\).
У вас есть \(n\) змеек (пронумерованных от \(1\) до \(n\)), которые нужно разместить в некоторых ячейках. Изначально каждая змейка занимает ровно одну ячейку, и вы не можете разместить более одной змейки в одной ячейке. После этого начинается игра.
Игра длится \(q\) секунд. Каждую секунду происходит один из двух типов событий:
- змейка \(s_i\) увеличивается: если змейка \(s_i\) занимала ячейки \([l, r]\), она увеличивается до отрезка \([l, r + 1]\);
- змейка \(s_i\) уменьшается: если змейка \(s_i\) занимала ячейки \([l, r]\), она уменьшается до отрезка \([l + 1, r]\).
Каждую секунду происходит ровно одно из событий.
Если в любой момент времени какая-либо змея наткнется на какое-либо препятствие (либо на другую змею, либо на конец полосы), вы проигрываете. В противном случае вы выигрываете со счетом, равным максимальной ячейке, занятой какой-либо змеей на данный момент.
Какой минимально возможный счет вы можете получить?
Примечание
В первом тесте оптимальная стратегия заключается в том, чтобы разместить вторую змею в ячейке \(1\), третью змею — в \(2\), а первую — в \(3\). Максимальная занятая ячейка — ячейка \(4\), и это минимально возможный результат.
Во втором тесте одна из оптимальных стратегий — следующая: нужно поставить
- змейку \(2\) в позицию \(1\);
- змейку \(3\) в позицию \(4\);
- змейку \(5\) в позицию \(6\);
- змейку \(1\) в позицию \(9\);
- змейку \(4\) в позицию \(10\).