Những viên đá của Kuriyama Mirai (Kuriyama Mirai's Stones)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Kuriyama Mirai có $n$ viên đá. Viên đá thứ $i$ có giá trị $v_i$.

Có hai cách xét dãy giá trị:

• dãy ban đầu $v_1,v_2,\ldots,v_n$;
• dãy thu được sau khi sắp xếp toàn bộ các giá trị theo thứ tự không giảm.

Bạn cần trả lời $m$ truy vấn. Mỗi truy vấn có dạng type l r:

• nếu type = 1, tính tổng các phần tử từ vị trí $l$ đến $r$ trong dãy ban đầu;
• nếu type = 2, tính tổng các phần tử từ vị trí $l$ đến $r$ trong dãy đã sắp xếp.

Hai dãy sử dụng cùng hệ chỉ số từ $1$ đến $n$.

Input

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $v_1,v_2,\ldots,v_n$.
• Dòng thứ ba chứa số nguyên $m$, là số truy vấn.
• Mỗi trong $m$ dòng tiếp theo chứa ba số nguyên type l r.

Output

Với mỗi truy vấn, in trên một dòng tổng tương ứng.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n,m\le10^5$

• $1\le v_i\le10^9$

• $type\in\{1,2\}$

• $1\le l\le r\le n$

• Subtask 1 — 20%: $n,m\le40$

• Subtask 2 — 30%: Mọi truy vấn đều có $type=1$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6

Output

24
9
28

Giải thích

Dãy ban đầu là

Sau khi sắp xếp không giảm, ta được

• Truy vấn 2 3 6 lấy các phần tử $4,6,7,7$ trong dãy đã sắp xếp, tổng bằng $24$.
• Truy vấn 1 3 4 lấy $2,7$ trong dãy ban đầu, tổng bằng $9$.
• Truy vấn 1 1 6 lấy toàn bộ dãy ban đầu, tổng bằng $28$.