time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Given a sequence of integers a₁, ..., a_n andq queries x₁, ..., x_q on it. For each queryx_i you have to count the number of pairs(l, r) such that 1 ≤ l ≤ r ≤ n and gcd(a_l, a_l + 1, ..., a_r) = x_i.

is a greatest common divisor ofv₁, v₂, ..., v_n, that is equal to a largest positive integer that divides allv_i.

Input

The first line of the input contains integer n, (1 ≤ n ≤ 10⁵), denoting the length of the sequence. The next line containsn space separated integers a₁, ..., a_n, (1 ≤ a_i ≤ 10⁹).

The third line of the input contains integer q, (1 ≤ q ≤ 3 × 10⁵), denoting the number of queries. Then followsq lines, each contain an integer x_i, (1 ≤ x_i ≤ 10⁹).

Output

For each query print the result in a separate line.

Sample test(s)

Input

32 6 3512346

Output

12201

Input

710 20 3 15 1000 60 16101234561020601000

Output

14022202211

题意给你一个序列和q个询问,输出有多少个区间[l,r]满足区间gcd为询问的值。

思路：处理出每一个区间的gcd(要注意合并区间)，假设有询问则直接加上去。

#include 
     
      using namespace std;std::map
      
        id;vector
       
        
          >gcdList;const int MAXN=100000+5;int query[MAXN*3],A[MAXN];long long ans[MAXN*3];int _gcd(int a,int b){return b?_gcd(b,a%b):a;}int ID(int x){    if(!id[x])id[x]=id.size();    return id[x];}int main(int argc, char const *argv[]){    int n;    ios_base::sync_with_stdio(false);    gcdList.clear();id.clear();    cin>>n;    for(int i=1;i<=n;i++)cin>>A[i];    int q;cin>>q;    for(int i=1;i<=q;i++){        cin>>query[i];        query[i]=ID(query[i]);    }    for(int i=1;i<=n;i++){        for(int j=0;j