珂朵莉的烦恼

Time Limit: 500 ms Memory Limit: 65536 KiB

Problem Description

                                                                                         

 

 身为黄金妖精族的珂朵莉(クトリ・ノタ・セニオリス)因为受到前世记忆的侵蚀,每天都在失去属于自己的记忆,而且珂朵莉并不能知道自己失去了多少宝贵的记忆,这让珂朵莉很是烦恼。

    现在我们有幸知道了珂朵莉每天失去的记忆的数量,珂朵莉希望你告诉她自第l天到第r天自己一共失去了多少记忆,由于失忆无时无刻不在进行,珂朵莉可能会问你很多次。你能正确的回答珂朵莉的问题么?

Input

     第一行包含一个数字 n,代表失忆发生的天数。( 0 <= n <= 1e6 )

     第二行包含 n 个数字,第 i 个数字代表珂朵莉在第 i 天丢失的记忆数。

     从第三行开始每行有两个由空格隔开的正整数 l , r 代表珂朵莉希望知道第 l 天到第 r 天自己丢失了多少记忆,输入以两个零结束。( 0 <= l <= r <= n )

     输入保证结果都在 int 范围内。

Output

    对于每次询问,输出一个非负整数代表在第 l 天到第 r 天里珂朵莉丢失了多少记忆。

Sample Input

5
1 2 3 2 1
1 1
1 5
0 0

Sample Output

1
9

Hint

本题时间限制严格,请使用scanf与printf进行输入输出。

Source

行走的二叉树