TopCoder

User's AC Ratio

100.0% (9/9)

Submission's AC Ratio

69.2% (9/13)

Tags

Description

很久很久以前,在人類尚未進入歷史時代時,位於現今的香港以西、福爾摩沙島以東、北極海以南、南極大陸以北之處,存在著一座無人記載的島嶼名為「小哩布拉西西里雅曉威海斯尼亞島」,簡稱「小島」。(別懷疑寫題敘的人,因為他是魔法師,所以他知道)那座小島的科技與文明都相當發達,已知用愛發電與說唱Freestyle。每位島民的智商與素質都比薹彎的記者還高。魔法師極度好奇是怎麼辦到的,於是決定帶著他的愛徒豬豬一同深入考古了解真相。
然而一切不是那麼的順利,正當他們搭乘時光&空間機前往小島時,卻遇到時間亂流。亂流將他們吹到2017年8月28日的某個神秘空間。因為魔法師在亂流內不小心撞到了頭,因此陷入昏厥狀態,魔法師漸漸回復意識之後,赫然發現豬豬被邪惡的野人囚禁。(因為魔法師在出發之前吃了許多翻譯蒟蒻,所以沒有語言不通的問題)邪惡的野人提出了邪惡的問題,要求魔法師必須用很快的速度回答且正確,才會放豬豬走,不然豬豬就會變成烤爐上的佳餚。
邪惡的野人問的問題如下:
你會獲得一個長度為$N$的序列,序列的編號方式為$1$ ~ $N$,對於每次野人的詢問,野人會告訴你兩個數字$L$,$R$,你必須回答第$L$項連加到第$R$項的數字總和是多少。(也就是$\sum_{i=L}^ {R} a_i $)
這時你一定會想到,只要魔法師隨便施展個魔法就可以救回豬豬了啊,但是魔法師因為撞到頭,忘記他自己是魔法師了。
身為旁觀者的你,目睹了整起事件的經過,內心的正義感驅使你發揮你的專長幫助魔法師與他的愛徒豬豬

Input Format

第一行輸入一個數字 $N$ $( 1 \le N \le 10 ^ 6 )$
接著輸入$N$個數字 $a_i$ $( 1 \le a_i \le 100 )$
接著輸入一個數字 $Q$ 代表有$Q$筆詢問 $( 1 \le Q \le 10 ^ 6)$
接著輸入$Q$行
每行有兩個數字$L$, $R$ $(1 \le L \le R \le N)$

Output Format

對於每筆詢問請輸出邪惡的野人要求的答案

Sample Input

10
1 2 3 4 6 5 7 9 8 10
5
1 5
2 4
1 10
6 6
5 9

Sample Output

16
9
55
5
35

Hints

子任務(測資)額外限制分數
1(0~2)$N \le 10 ^ 3, Q \le 10 ^ 3$40
2(3~4)$N \le 10 ^ 5, Q \le 10 ^ 5$7
3(5~7)53

某一年大發明家拉胖與他的團隊發明了一整套的懶人用具,讓島民一整年都不用離開床也能生活下去,導致島上的胖子越來越多,從那年起小島每年往下沉71公尺,在22年後,終於整個沈沒於海中。

Problem Source

Problem set by 魔法師(Polarz)

Subtasks

For Testdata: 0 ~ 2, Score: 40
For Testdata: 3 ~ 4, Score: 7
For Testdata: 5 ~ 7, Score: 53
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 5000 65536 65536
6 1000 65536 65536
7 1000 65536 65536