У вас есть робот, который двигается по числовой прямой. В момент времени \(0\) он находится в точке \(0\).
Вы посылаете роботу \(n\) команд: в \(t_i\)-ю секунды вы указываете робот пойти в точку \(x_i\). Когда робот получает команду, он сразу же начинает движение в сторону точки \(x_i\) со скоростью \(1\) в секунду и останавливается, когда достигает этой точки. Однако, когда робот двигается, он игнорирует все другие команды, которые он получает.
Например, предположим, что роботу приходят три команды: в секунду \(1\) ехать в точку \(5\), в секунду \(3\) ехать в точку \(0\) и в секунду \(6\) ехать в точку \(4\). Тогда робот будет стоять в \(0\) до секунды \(1\), затем начнет ехать к \(5\), игнорируя вторую команду, достигнет \(5\) в момент времени \(6\) и сразу же начнет ехать к \(4\), чтобы выполнить третью команду. В момент времени \(7\) он доедет до \(4\) и остановится там.
Команда \(i\) считается выполненной успешно, если существует такой момент времени в отрезке \([t_i, t_{i + 1}]\) (то есть после того, как команда послана, и перед тем, как послана следующая, обе границы включительно; считаем \(t_{n + 1} = +\infty\)), что робот находится в позиции \(x_i\). Посчитайте количество успешных команд. Обратите внимание, что проигнорированная команда все равно может быть успешной.
Примечание
Движение робота в первом наборе входных данных описано в условии задачи. Только последняя команда успешна.
Во втором наборе входных данных вторая команда успешна: робот проходит через точку назначения \(4\) в момент времени \(5\). К тому же, последняя команда тоже в конце концов станет успешной.
В третьем наборе входных данных ни одна команда не успешна, и робот остановится в \(-5\) в секунду \(7\).
Вот \(0\)-индексированные последовательности позиций робота в каждую секунду для каждого набора входных данных из примера. Все отрезанные позиции совпадают с последней:
- \([0, 0, 1, 2, 3, 4, 5, 4, 4, \dots]\)
- \([0, 0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -5, \dots]\)
- \([0, 0, 0, -1, -2, -3, -4, -5, -5, \dots]\)
- \([0, 0, 0, 0, 1, 2, 3, 3, 3, 3, 2, 2, 2, 1, 0, 0, \dots]\)
- \([0, 0, 1, 0, -1, -2, -3, -4, -5, -6, -6, -6, -6, -7, -8, -9, -9, -9, -9, -8, -7, -6, -5, -4, -3, -2, -1, -1, \dots]\)
- \([0, 0, -1, -2, -3, -4, -4, -3, -2, -1, -1, \dots]\)
- \([0, 0, 1, 2, 2, \dots]\)
- \([0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -7, \dots]\)