子数组最大公约数查询

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定正整数序列 $a_1\ldots a_n$。每个查询给出 $x$，求满足 $\gcd(a_l,\ldots,a_r)=x$ 的非空连续子数组 $(l,r)$ 数量。

输入格式

第一行是 $n$，第二行是 $n$ 个整数。第三行是查询数 $q$，随后 $q$ 行每行一个整数 $x$。

输出格式

对每个查询单独输出一行答案。

样例输入 1

3
2 6 3
5
1
2
3
4
6

样例输出 1

1
2
2
0
1

数据范围

• $1\le n\le10^5$；
• $1\le a_i\le10^9$；
• $1\le q\le3\times10^5$；
• $1\le x\le10^9$。

本题采用独立测试点计分，每个测试点等分。