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

The first line of the input contains integer $n$, ($1 \le n \le 10^5$), denoting the length of the sequence. The next line contains $n$ space separated integers $a_1, \dots, a_n$, ($1 \le a_i \le 10^9$). The third line of the input contains integer $q$, ($1 \le q \le 3 \times 10^5$), denoting the number of queries. Then follows $q$ lines, each contain an integer $x_i$, ($1 \le x_i \le 10^9$).

For each query print the result in a separate line.