题目背景
不称职的懦弱少女程心被选来充当掌握地球命运的执剑人，她因为罗辑的成功将这看作一项只需花费时间的任务，刚刚任职水滴就向地球发动攻击，程心为了忠于人性做出了错误的决定。在警示下继续逃离的“蓝色空间”号，受到具有发射引力波能力的“万有引力”号与两个同行的“水滴”追击，其上的人员进入四维空间摧毁水滴并占领了“万有引力”号，启动引力波广播向宇宙公布了三体星系的坐标。
云天明与地球取得联系，通过讲述三个自己编创的童话故事，向程心透露大量情报；人类自以为悟出了生存竞争的秘密，开始进行掩体计划，维德领导的空间曲率驱动研究因为程心的错误判断被终止，使得人类最终没有能够逃脱被高级文明毁灭的命运。因为宇宙中还存在更强大的文明，战争的方式和武器已经远超出人类的想象，极高文明发出了一张卡片大小的“二向箔”，使整个太阳系压缩为二维平面而毁灭。
在地球人类接近灭亡之际，只有程心和艾AA两个幸存者乘坐光速飞船离开。罗辑成为设置于冥王星的地球文明博物馆的“守墓人”，她们在冥王星带走人类文明的精华。在云天明送的恒星的一颗行星上，程心遇到关一帆且探讨了宇宙降维的真相，然而超乎一切之上的力量要求宇宙归零重生，在黑域中穿越长达1800万年的时空……程心没有等到云天明到来，和关一帆在小宇宙中短暂居住后重新进入大宇宙生活
题目描述
在《三体》故事中，程心接任了掌握地球命运的“执剑人”角色，面对强大文明的威胁，她在关键时刻做出了错误的决策，导致了地球文明的毁灭。为了逃避毁灭的命运，程心和艾AA乘坐光速飞船逃离，但在逃亡过程中，她们遇到了一个重要的抉择问题：
-
在逃亡过程中，程心和艾AA乘坐的飞船遇到了多个光速传送门，这些传送门之间有不同的时间延迟。在每个传送门的过程中，如果传送门的延迟超过一定时间限制，它们就会错过宇宙中唯一的安全通道，导致飞船被其他未知力量捕获。程心需要尽快选择一条最优的路径，并决定如何选择最佳的传送门，以使她们能够尽可能快地逃出。
-
然而，飞船的能量有限，程心只能选择在指定时间内穿越一些传送门，并且每个传送门的延迟时间不同。程心的任务是选择那些延迟时间总和最小的传送门路径，使她们能够顺利到达安全区域。
输入格式
- 第一行输入一个整数
n（1 ≤ n ≤ 10^5），表示传送门的数量。 - 第二行输入
n个整数a1, a2, ..., an（1 ≤ ai ≤ 10^9），表示每个传送门的延迟时间（单位：秒）。 - 第三行输入一个整数
m（1 ≤ m ≤ 10^5），表示程序需要处理的查询次数。 - 接下来
m行，每行输入两个整数l和r（1 ≤ l ≤ r ≤ n），表示在给定的时间段[l, r]之间选择传送门的延迟时间总和。
其中：
1 ≤ n ≤ 10^5
1 ≤ m ≤ 10^5
1 ≤ ai ≤ 10^9
输出格式
对于每个查询，输出一个整数，表示区间 [l, r] 内所有传送门的延迟时间总和的最小值。
样例
Input 1
5
10 20 30 15 25
3
1 3
2 4
1 5
Output 1
10
15
10