Frets On Fire

Frets On Fire

Miyako came to the flea kingdom with a ukulele. She became good friends with local flea residents and played beautiful music for them every day.

In return, the fleas made a bigger ukulele for her: it has nn strings, and each string has (1018+1)(1018+1) frets numerated from 00 to 10181018. The fleas use the array s1,s2,…,sns1,s2,…,sn to describe the ukulele’s tuning, that is, the pitch of the jj-th fret on the ii-th string is the integer si+jsi+j.

Miyako is about to leave the kingdom, but the fleas hope that Miyako will answer some last questions for them.

Each question is in the form of: “How many different pitches are there, if we consider frets between ll and rr (inclusive) on all strings?”

Miyako is about to visit the cricket kingdom and has no time to answer all the questions. Please help her with this task!

Formally, you are given a matrix with nn rows and (1018+1)(1018+1) columns, where the cell in the ii-th row and jj-th column (0≤j≤10180≤j≤1018) contains the integer si+jsi+j. You are to answer qq queries, in the kk-th query you have to answer the number of distinct integers in the matrix from the lklk-th to the rkrk-th columns, inclusive.

Input

The first line contains an integer nn (1≤n≤1000001≤n≤100000) — the number of strings.

The second line contains nn integers s1,s2,…,sns1,s2,…,sn (0≤si≤10180≤si≤1018) — the tuning of the ukulele.

The third line contains an integer qq (1≤q≤1000001≤q≤100000) — the number of questions.

The kk-th among the following qq lines contains two integers lklk，rkrk (0≤lk≤rk≤10180≤lk≤rk≤1018) — a question from the fleas.

Output

Output one number for each question, separated by spaces — the number of different pitches.

Examples

Input

63 1 4 1 5 937 70 28 17

Output

5 10 18

Input

21 50000000000000000021000000000000000000 10000000000000000000 1000000000000000000

Output

2 1500000000000000000

Note

For the first example, the pitches on the 66 strings are as follows.

Fret	0	1	2	3	4	5	6	7	…	
s1:		3	4	5	6	7	8	9	10	…	
s2:		1	2	3	4	5	6	7	8	…	
s3:		4	5	6	7	8	9	10	11	…	
s4:		1	2	3	4	5	6	7	8	…	
s5:		5	6	7	8	9	10	11	12	…	
s6:		9	10	11	12	13	14	15	16	…

There are 5 different pitches on fret 77 — 8,10,11,12,168,10,11,12,16.

There are 10 different pitches on frets 0,1,20,1,2 — 1,2,3,4,5,6,7,9,10,111,2,3,4,5,6,7,9,10,11.

一.题解及分析

本题的思考角度比较特殊 , 应通过每一行(经过排序)贡献的数字个数(min(每一行的元素个数,下一行首项与这一行的首项之差))的和(最后一行计作该行的元素个数)来计算总的不同的个数 , 通过二分法找到小于等于每一行的元素个数的最后一项的下标 .

#include<stdio.h>//M - Frets On Fire
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
long long int s[1000005],total[1000005];
long long int t[1000005];
unsigned long long int sum=0;
long long int n;
int main()
{
    long long int q;
    scanf("%lld",&n);
    for(long long int i=1;i<=n;i++)
    {
        scanf("%lld ",&s[i]);
    }
    memset(total,0,sizeof(total));
    sort(s+1,s+n+1);
    for(long long int i=1;i<n;i++)
    {
        t[i]=s[i+1]-s[i];          
    }
    sort(t+1,t+n);
    //必须要在循环外面先预处理加到第几项的和是多少,如果放在循环里面就会超时
    for(long long int i=1;i<n;i++)
    {
        total[i]=total[i-1]+t[i];
    }
    scanf("%lld",&q);
    while(q--)
    {
        long long int r,l,weizhi;
        scanf("%lld%lld",&l,&r);
        r=r-l+1;
        //下面是找到小于等于r的最后一项的下标
        weizhi=upper_bound(t+1,t+n,r)-t-1;//注意是(t+1,t+n,r),不是(t+1,t+n-1,r)一共有n-1个元素
        sum=total[weizhi]+(n-weizhi)*r;
        printf("%llu\n",sum);
    }
    return 0;
}