B. Куряама Мирагийн чулуунууд

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

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

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

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

Куряама Мира олон мангас алсан бөгөөд түүнд олон чулуунууд (тухайлбал $n$) байгаа. Тэр чулуунуудаа $1$-с $n$ хүртэл дугаарлав. $i$-р чулууны үнэ нь $v_{i}$. Куряама Мира чулуунуудыхаа талаар зарим нэг зүйлийг мэдэхийг хүссэн учраас чамаас хоёр төрлийн асуулт асууж байна:

  1. Тэр чамд $l$ ба $r (1 ≤ l ≤ r ≤ n)$ хоёр тоо хэлэх бөгөөд чи түүнд нийлбэрийг хэлэх ёстой.
  2. $u_{i}$ бол чулууны $i$-р хамгийн хямд үнэ гэж бодъё (хэрвээ бид бүх чулууны үнийг үл буурах дарааллаар зохион байгуулсан бол $i$-р байрлалд байгаа үнэ). Энэ удаад тэр бидэнд $l$ ба $r (1 ≤ l ≤ r ≤ n)$ хоёр тоог хэлэх бөгөөд түүнд нийлбэрийг хэлэх ёстой.

Чи түүнд асуулт бүрийн зөв хариултыг өгөх ёстой, үгүй бол Куряама Мира "fuyukai desu" гэж хэлээд гунигтай болно.

Оролт

Эхний мөрөнд $n (1 ≤ n ≤ 10^{5})$ бүхэл тоог оруулна. Хоёр дахь мөр $n$ бүхэл тоонууд агуулна: $v_{1}, v_{2}, ..., v_{n} (1 ≤ v_{i} ≤ 10^{9})$. Эдгээр нь чулуунуудын үнэ юм.

Гурав дахь мөрөнд Куряама Мирагийн асуултын тоо болох $m (1 ≤ m ≤ 10^{5})$ бүхэл тоог оруулна. Дараа нь $m$ мөрүүд байх ба мөр бүр нь $type$, $l$, $r$ $(1 ≤ l ≤ r ≤ n; 1 ≤ type ≤ 2)$ гэсэн гурван бүхэл тоо агуулна. Хэрвээ $type$ нь $1$-тэй тэнцүү бол чи эхний асуултын хариуг буцаана, үгүй бол хоёрдугаар асуултын хариуг буцаах ёстой.

Гаралт

Мөр бүр нь бүхэл тоо агуулсан $m$ мөрүүд хэвлэнэ. Эдгээр нь Куряама Мирагийн асуултын хариултууд байна. Асуултыг оруулсан дарааллаар хариултыг хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6
Гаралт
24
9
28
Оролт
4
5 5 2 3
10
1 2 4
2 1 4
1 1 1
2 1 4
2 1 2
1 1 1
1 3 3
1 1 3
1 4 4
1 2 2
Гаралт
10
15
5
15
5
5
2
12
3
5

Тэмдэглэл

Асуултын хариулт нь 32-битийн бүхэл тооноос хэтэрч болно гэдгийг анхаарна уу.

Сэтгэгдлүүдийг ачааллаж байна...