Дан массив неотрицательных чисел длины n. Необходимо отвечать на запросы: какое максимальное количество чисел из начала массива можно взять, чтобы их сумма не превосходила x? Время на один запрос — O(log n). Можно ли решить задачу таким же образом, если

Пусть у нас дан массив a[0…n–1] и имеется набор запросов: для данного x найти такое максимальное k, что сумма a[0] + a[1] + … + a[k–1] не превосходит x.

1. Если все числа неотрицательные.
   
   а) Предварительно вычислим массив префиксных сумм S, где S[0] = 0, S[i] = S[i–1] + a[i–1] для i = 1…n.
   б) Заметим, что при условии неотрицательности элементов S монотонно возрастает, то есть S[i+1] ≥ S[i].
   в) Тогда ответ на запрос можно найти бинарным поиском: ищем максимальное i такое, что S[i] ≤ x.
   г) Бинарный поиск даст время ответа O(log n) на запрос.<br...