Задача №114976. Выращивание кроликов
Разочаровавшись в олимпиадной информатике после школьного этапа, маленький мальчик Захар решил заняться разведением кроликов. Для этого он купил себе \(n\) кроликов и пронумеровал их по неубыванию весов. Изначально \(i\)-й кролик весит \(w_i\) килограмм.
Захар заметил, что если кроликов выстроить в шеренгу в порядке неубывания весов, то каждый день у каждого кролика, такого что его вес меньше веса следующего, вес увеличивается на 1 килограмм. Более формально, каждый день вес \(i\)-го кролика увеличивается на \(1\) кг, если он не последний в шеренге, и \(w_i \neq w_{i + 1}\). Все такие изменения происходят одновременно для всех кроликов. Такое происходит до тех пор, пока веса всех кроликов не становятся равными весу последнего кролика в шеренге.
Захар очень любознательный мальчик, а поэтому ему хочется ответить на \(m\) запросов: через сколько дней вес кроликов больше не будет меняться, если в качестве шеренги взять кроликов с номерами от \(l_i\) до \(r_i\). Так как Захар разочарован в олимпиадной информатике, помочь ему предстоит вам.
В первой строке задано единственное целое число \(n\) (\(1 \leq n \leq 200\,000\)) — количество кроликов у Захара.
В следующей строке заданы \(n\) целых чисел \(w_1, w_2, \ldots, w_n\) (\(1 \leq w_i \leq 10^{9}\)) — веса кроликов. Гарантируется, что эти числа отсортированы по неубыванию, то есть \(w_i \leq w_{i + 1}\), для всех \(i \le n - 1\).
В следующей строке задано единственное целое число \(m\) (\(1 \leq m \leq 200\,000\)) — количество запросов.
В следующих \(m\) строках задано по два целых числа \(l_i\) и \(r_i\) (\(1 \leq l_i \leq r_i \leq n\)) — границы шеренги из \(i\)-го запроса.
На каждый запрос в отдельной строке выведите количество дней, после которых веса кроликов не будет меняться. Можно показать, что такой день обязательно наступит.
В первом запросе после первого дня веса были равны \(1, 3, 3, 7\), после второго \([2, 3, 4, 7]\), третьего \([3, 4, 5, 7]\), \([4, 5, 6, 7]\), \([5, 6, 7, 7]\), \([6, 7, 7, 7]\) и после седьмого \([7, 7, 7, 7]\)
Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(w\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 14 | \(n \le 100\) | \(m \le 100\) | \(w \leq 100\) | 0 | |
| 2 | 17 | \(n \le 500\) | \(m \le 500\) | \(w \leq 500\) | 0, 1 | |
| 3 | 23 | \(n \le 10\,000\) | \(m \le 10\,000\) | – | 0, 1, 2 | |
| 4 | 12 | \(n \leq 100\,000\) | \(m \leq 100\,000\) | \(w \leq 2\) | – | |
| 5 | 13 | \(n \leq 100\,000\) | \(m \leq 100\,000\) | \(w \leq 1000\) | 0, 1, 2, 4 | |
| 6 | 21 | – | – | – | 0 – 5 | Offline-проверка |
4 1 3 3 7 4 1 4 1 3 2 4 2 3
6 2 5 0