E. Функц

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Серега, Федор нар функцээр тоглодог. Нэг өдөр тэд маш сонирхолтой функцтэй ирлээ. Энэ нь:

  • $f(1, j) = a[j]$, $1 ≤ j ≤ n$.
  • $f(i, j) = min(f(i - 1, j), f(i - 1, j - 1)) + a[j]$, $2 ≤ i ≤ n$, $i ≤ j ≤ n$.

Энд $a$ нь $n$ урттай (элементтэй) бүхэл тоон дараалал.

Серега, Федор нар энэ функцийн зарим цэг дээрх утгыг олохыг хүсчээ. Гэвч тэд үүнийг гараар тооцохыг хүссэнгүй. Тэгэхээр тэд тусламж хүсч байна.

Оролт

Эхний мөр $a$ дарааллын урт болох $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоог агуулна. Дараагийн мөрөнд $n$ ширхэг бүхэл тоо $a[1], a[2], ..., a[n]$ ($0 ≤ a[i] ≤ 10^{4}$) байрлана.

Дараагийн мөрөнд хүсэлтүүдийн тоо $m$ $(1 ≤ m ≤ 10^{5})$ байрлана. Үүний дараагийн $m$ мөр бүрт $x_{i}$, $y_{i}$ ($1 ≤ x_{i} ≤ y_{i} ≤ n$) хоёр бүхэл тоо байрлана. Эдгээр мөр бүр нь Федор, Серега нар $f(x_{i}, y_{i})$ утгыг олохыг хүсч байгааг илтгэнэ.

Гаралт

$m$ мөрөнд залуусын хүсэлтийн хариуг хэвлэ.

Орчуулсан: Sugardorj

Жишээ тэстүүд

Оролт
6
2 2 3 4 3 4
4
4 5
3 4
3 4
2 3
Гаралт
12
9
9
5
Оролт
7
1 3 2 3 4 0 2
4
4 5
2 3
1 4
4 6
Гаралт
11
4
3
0
Сэтгэгдлүүдийг ачааллаж байна...