вопросы даются оффлайн, подумай что это тебе дает?
подсказка 1:
реши сначала для n <= 5000 и q <= 5000, посмотри что ты делаешь, может это можно как-то ускорить?
подсказка 2:
в решение за nq ты просто пробегаешься по массиву и ищешь следующий с большим диаметром и т.д, если ты отсортируешь запросы в убывающем порядке и будешь бежать с конца, можешь ли ты ускорить этот процесс?
подсказка 3:
давай будем хранить вектор для каждой такой пока сущесвутющей возврастающей последовательности, на нем можно бинпоиском искать первый момент когда суммарно хватит объема чтобы весь v покрыть(ну или найти что такого нету), подумай как быстро сумму на суффиксе вектора находить
подсказка 4:
давай будем хранить текующую сумму на возрастающей последовательности, и когда добавлять вектор добавлять и ее, так ты сможешь с помощью суффиксных сумм находить сумму на суффиксе за O(1)