Codeforces Global Round 2 1119D. Frets On Fire【差分+前缀和+二分】

D. Frets On Fire

time limit per test

1.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Copy

6
3 1 4 1 5 9
3
7 7
0 2
8 17

output

Copy

5 10 18

input

Copy

2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000

output

Copy

2 1500000000000000000

Note

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

 

Frets1:s2:s3:s4:s5:s6:031415914252610253637113647481247585913586961014697107111571081181216…………………Fret01234567…s1:345678910…s2:12345678…s3:4567891011…s4:12345678…s5:56789101112…s6:910111213141516…

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

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

 

 

题意：略。

分析：因为l,r都是1e18的范围，所以必然是一道推公式的题，q<=1e5，那么每个询问至多log的复杂度。

同时，[l,r]与[0,r-l]的询问没有本质上的区别，所以我们把[l,r]等效成[0,r-l]

我们首先吧数组里的最小值和最大值取出来，那么所有数的范围一定在[min,max+r-l]之间，可知[min,max+r-l]中可能会有空隙也可能会没有，这取决于这个数组的差分数组和r-l的大小关系。

那么我们先把原数组排序并且差分，得到数组d，d[i]对应s[i]和s[i+1]。

单独考虑每一个d[i]，如果d[i]<=r-l+1 那么s[i]到s[i+1]的数必然全部存在，否则，中间少了r-l+1-d[i]个数。

那么接下来就很简单了，将d数组排序，并求一个前缀和，二分查找d数组中比r-l+1大的，就可以在logN的复杂度中计算出ans。

#include "bits/stdc++.h"
using namespace std;
long long s[100004];//原数组
long long d[100004];//差分数组，这里我记录的是差分-1，若直接记录差分的话，后面表达式需要修改
long long pre[100004];//差分数组前缀和
int main()
{
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i) {
        scanf("%lld",&s[i]);
    }
    sort(s,s+n);
    for (int i = 0; i < n-1; ++i) {
        d[i]=s[i+1]-s[i]-1;
    }
    sort(d,d+n-1);
    pre[0]=d[0];
    for (int i = 1 ;i < n-1; ++i) {
        pre[i]=pre[i-1]+d[i];
    }
    long long mini=s[0],maxi=s[n-1];
    int q;
    cin>>q;
    while(q--)
    {
        long long l,r;
        scanf("%lld%lld",&l,&r);
        long long x=r-l;
        long long pos=upper_bound(d,d+n-1,x)-d;
        long long ans=maxi+x-mini+1-(pre[n-2]-pre[pos-1])+(n-1-pos)*x;
        printf("%lld ",ans);
    }
}