yg学长的舍友fjk每天的学习计划就是总是在基础的作业量上少写a_i道题，日积月累之下fjk警觉自己少写的题越来越多。一共n天，每天fjk都会少写a_i道题，由于不喜欢学习导致fjk的算数能力越来越差，它向你发出了q次询问，每次询问都会给出两个整数l，r，表示fjk向你询问它从第l天到第r天（包含第l天和第r天）一共少写了多少题。

第一行给出一个正整数n（1 <= n <= 1e5）
第二行给出n个正整数ai，表示第i天fjk少写了多少道题（0 <= a_i <= 1e10）
第三行给出一个正整数q（1 <= q <= 1e5）
接下来的q行每行两个正整数l，r（1 <= l,r <= n）

对于每次询问在一行中输出一个正整数表示fjk从第l天到第r天一共少写了多少道题。

数据范围较大注意超时，需要使用更高效的算法解决此问题。