Иван играет в старый шутер под названием «Heretic». Он застрял на одном из последних уровней этой игры, поэтому ему нужна помощь в убийстве монстров.
Основная часть уровня представляет собой большой коридор (настолько большой и узкий, что его можно представить в виде бесконечной координатной прямой). Коридор разделен на две части; давайте считать, что точка \(x = 0\) разделяет эти части.
Правая часть коридора заполнена \(n\) монстрами. Для каждого монстра задана его начальная координата \(x_i\) (поскольку все монстры находятся в правой части, все \(x_i\) положительны).
Левая часть коридора заполнена ловушками-давилками. Если какой-то монстр попадает в левую часть коридора или в начало координат (то есть его текущая координата становится меньше или равна \(0\)), он мгновенно убивается ловушкой.
Основным оружием, которое Иван использует для убийства монстров, является Жезл Феникса. Он может запустить снаряд, который взрывается при ударе, уничтожая каждого монстра, оказавшегося в точке взрыва, и разбрасывая всех остальных монстров. Предположим, что Иван запускает снаряд в точку \(c\). Тогда каждый монстр либо погибает от взрыва, либо отбрасывается. Пусть текущая координата какого-то монстра будет \(y\), тогда:
- если \(c = y\), то монстр убит;
- если \(y < c\), то монстр отбрасывается на \(r\) влево, поэтому его текущая координата становится \(y - r\);
- если \(y > c\), то монстр отбрасывается на \(r\) вправо, поэтому его текущая координата становится \(y + r\).
Иван собирается убивать монстров следующим образом: выбирать некоторую целочисленную точку \(d\), запускать снаряд в эту точку, затем ждать, пока снаряд не взорвется, и все монстры, которых отбрасывает в левую часть коридора, не будут убиты ловушками-давилками, затем, если хотя бы один монстр еще жив, выбирать другую целую точку (возможно, ту, которая уже использовалась) и запускать снаряд туда, и так далее.
Какое минимальное количество снарядов должен запустить Иван, чтобы убить всех монстров? Можете считать, что Иван оптимально выбирает цель, когда стреляет из Жезла Феникса.
Вам нужно ответить на \(q\) независимых запросов.