CF475D.CGCDSSQ

Given a sequence of integers _a_1, ..., a__n and q queries _x_1, ..., x__q on it. For each query x__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 of _v_1, _v_2, ..., v__n, that is equal to a largest positive integer that divides all v__i.

给定一个整数序列 $a_1, \dots, a_n$ 和 $q$ 个查询 $x_1, \dots, x_q$。对每个查询 $x_i$，你需要统计满足 $1 \le l \le r \le n$ 且 $\gcd(a_l, a_{l+1}, \dots, a_r) = x_i$ 的区间对 $(l, r)$ 的数量。

表示 $v_1, v_2, \dots, v_n$ 的最大公约数（GCD），即能整除所有 $v_i$ 的最大正整数。

The first line of the input contains integer n, (1 ≤ n ≤ 105), denoting the length of the sequence. The next line contains n space separated integers _a_1, ..., a__n, (1 ≤ a__i ≤ 109).

The third line of the input contains integer q, (1 ≤ q ≤ 3 × 105), denoting the number of queries. Then follows q lines, each contain an integer x__i, (1 ≤ x__i ≤ 109).

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示序列的长度。
第二行包含 $n$ 个以空格分隔的整数 $a_1, \ldots, a_n$（$1 \leq a_i \leq 10^9$）。

输入的第三行包含一个整数 $q$（$1 \leq q \leq 3 \times 10^5$），表示查询的次数。
随后是 $q$ 行，每行包含一个整数 $x_i$（$1 \leq x_i \leq 10^9$）。

For each query print the result in a separate line.

对每个查询，在单独的一行中输出结果。