Попарний добуток

Вхідні дані

Перший рядок містить одне число $n$ ( $2 \leq n \leq 2 \cdot 1 0^{5}$ 2\le n\le 2\cdot 10^5) — розмір масиву $a$ .

Другий рядок містить $n$ цілих чисел $a_{1}, \dots, a_{n}$ a_1,\dots,a_n $(1 \leq a_{i} \leq 1 0^{9})$ (1\le a_i\le 10^9) — елементи масиву.

Третій рядок містить одне ціле $q$ ( $1 \leq q \leq 2 \cdot 1 0^{5}$ 1\le q\le 2\cdot 10^5) — кількість запитів.

Кожен з наступних $q$ рядків містить по два цілі числа $l$ та $r$ ( $1 \leq l < r \leq n$ 1\le l<r\le n).

Вихідні дані

Виведіть $q$ рядків — відповідь до кожного запиту.

Приклади

Приклад

Loading

Приклад 1

Loading

Приклад 2

Loading

Оцінювання

У цій задачі існують умовні блоки. Якщо ваше рішення буде працювати правильно для певних обмежень, то воно отримуватиме певну кількість балів. Зверніть увагу, що оцінювання й досі потестове.

( $29$ балів): $n \leq 100$ n\le 100, $q \leq 100$ q\le100;
( $36$ балів): $n \leq 10000$ n\le 10\,000, $q \leq 100$ q\le 100;
( $35$ балів): без додаткових обмежень.