В стране енотов есть n городов, расположенных в ряд. Еноты любят гигантские ёлки, каждую из которых они устанавливают так, что она накрывает города с номерами в отрезке чётной длины от l до r включительно. Ёлочным треугольником последовательности b1, ..., bk чётной длины назовём набор последовательностей Ti. Первая последовательность совпадает с данной (T1 = b1, ..., bk), а каждая из оставшихся получена удалением первого и последнего элемента из предыдущей (Ti = bi, ..., bk - i + 1). Например, ёлочный треугольник последовательности 1, 2, 3, 4, 5, 6 выглядит так:

Ёлкой последовательности c1, ..., ck чётной длины называется последовательность ёлочных треугольников последовательностей S1, ..., Sk/2, где Si = ci, ..., ck - i + 1. При этом центр каждого треугольника совпадает с центром ёлки. Например, ёлка последовательности 1, 2, 3, 4, 5, 6 выглядит так:

В каждом городе есть свой вид украшений: в i-м городе красота украшений равна ai. Когда еноты устанавливают гигантскую ёлку, накрывающую города с номерами в отрезке [l, r], то каждый город под этой ёлкой вешает свои украшения на все позиции в ёлке, под которыми этот город находится. Например, если накрыто шесть городов, то четвёртый накрытый город вешает украшения на все позиции, обозначенные четвёркой на рисунке выше.

Красота ёлки - сумма значений красоты каждого использованного украшения.

Вам даны значения красоты украшений, используемых в каждом городе, и описания k гигантских ёлок, которые ставили еноты. Енот Дмитрий хочет работать аналитиком, и в качестве тестового задания ему предложили упорядочить данный вам список из ёлок по возрастанию значений красоты. С сортировкой он справится и сам, а найти значения красоты каждой ёлки он попросил вас.

Поскольку красота ёлки может быть очень большой, достаточно найти её значение по модулю 998244353.

Формат входных данных

В первой строке задано число n (2 ≤ n ≤ 1000000) - число городов.

Во второй строке через пробел заданы n чисел a1, a2, ..., an (1 ≤ ai ≤ 109) - красота украшений, используемых в каждом из городов.

В третьей строке задано число k (1 ≤ k ≤ 1000000) - число ёлок.

В i-й из последующих k строк содержатся два числа l и r (1 ≤ l < r ≤ n) - номера первого и последнего городов, которые украшают ёлку с номером i. Гарантируется, что этот диапазон чётной длины, то есть (r - l + 1) делится на 2.

Формат результата

Необходимо вывести k строк, i-я из которых содержит суммарную красоту украшений на i-й ёлке по модулю 998244353.

Примеры

Входные данные

6
1 2 3 4 5 6
3
1 6
1 4
2 5
Результат работы

70
20
28
Входные данные

6
3 1 2 2 1 2
2
2 5
1 4
Результат работы

14
14
Примечания

Система оценки:

Решения, верно работающие при n, k ≤ 40, будут получать не менее 20% . Решения, верно работающие при n, k ≤ 5000, будут получать не менее 50% .

173

429

Посмотреть ответы 1

Ответы на вопрос:

няшкаморскаясвинка

Информатика

4,7(16 оценок)

Var a, b, c : integer; begin read (a, b, c); if a = b then begin a : = sqr (a); b : = sqr (b); c : = sqr (c); end else if (a > b) and (b > c) then begin b : = a; c : = a; end else begin a : = b + c; c : = 0; end; write (a, ' ', b, ' ', c); end.

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Информатика

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.