Это — усложненная версия задачи. Единственное различие в том, что в данной версии \(1 \le q \le 10^5\). Вы можете взламывать другие решения, только если решены обе версии задачи.
Рассмотрим процесс, проходящий на массивах \(a\) и \(b\) длины \(n\) и \(n-1\) соответственно.
Процесс — это бесконечная последовательность действий. Каждое действие имеет следующий вид:
- Сначала, выберем случайное целое число \(i\) (\(1 \le i \le n-1\)).
- Теперь, одновременно присвоим \(a_i = \min\left(a_i, \frac{a_i+a_{i+1}-b_i}{2}\right)\) и \(a_{i+1} = \max\left(a_{i+1}, \frac{a_i+a_{i+1}+b_i}{2}\right)\) без округлений (то есть значения могут перестать быть целыми).
Пример такой операции представлен в заметках.
Можно доказать, что массив \(a\) сходится, т. е. для каждого \(i\) существует предел, к которому \(a_i\) сходится. Пусть функция \(F(a, b)\) возвращает значение, к которому сходится \(a_1\), в результате процесса на массивах \(a\) и \(b\).
Вам задан массив \(b\), но не массив \(a\). Однако вам задан третий массив \(c\). Назовем массив \(a\) хорошим, если он состоит из целых чисел и удовлетворяет неравенству \(0 \leq a_i \leq c_i\) для всех \(1 \leq i \leq n\).
Ваша задача — посчитать количество хороших массивов \(a\), для которых \(F(a, b) \geq x\), для \(q\) значений \(x\). Так как ответ может быть слишком большим, выведите его по модулю \(10^9+7\).
Выходные данные
Выведите \(q\) целых чисел, где \(i\)-е число — ответ на \(i\)-й запрос, т. е. количество хороших массивов \(a\) с \(F(a, b) \geq x_i\) по модулю \(10^9+7\).
Примечание
Объяснение далее предполагает, что \(b = [2, 1]\) и \(c=[2, 3, 4]\) (как в примере).
Примеры массивов \(a\), которые не являются хорошими:
- \(a = [3, 2, 3]\) не является хорошим, потому что \(a_1 > c_1\);
- \(a = [0, -1, 3]\) не является хорошим, потому что \(a_2 < 0\).
Один из возможных хороших массивов \(a\) — это \([0, 2, 4]\). Можно показать, что ни одна операция его не изменит, а потому \(F(a, b) = a_1 = 0\).
Другой возможных хороший массив \(a\) — это \([0, 1, 4]\). За одну операцию с \(i = 1\) мы присваиваем \(a_1 = \min(\frac{0+1-2}{2}, 0)\) и \(a_2 = \max(\frac{0+1+2}{2}, 1)\). То есть, после одной операции с \(i = 1\), \(a\) становится равен \([-\frac{1}{2}, \frac{3}{2}, 4]\). Можно показать, что далее ни одна операция не изменит массив, а потому \(F(a, b) = -\frac{1}{2}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3 4
2 1
5
-1 0 1 -100000 100000
|
56
28
4
60
0
|