Informática Avançado - Semana 71

Colônia de Formigas

Mole é um tamanduá, e está com muita fome. Ele encontrou uma colônia de formigas, composta por $n$ formigas, ordenadas em sequência. Cada formiga $i$ $(1 \leq i \leq n)$ tem uma força $s_i$.

Para tornar seu jantar mais interessante, Mole organiza uma versão dos «Jogos Vorazes» para as formigas. Ele escolhe dois números $l$ e $r$ $(1 \leq l \leq r \leq n)$ e cada par de formigas com índices entre $l$ e $r$ (inclusive) lutará. Quando duas formigas $i$ e $j$ lutam, a formiga $i$ obtém um ponto de batalha apenas se $s_i$ divide $s_j$ (também, formiga $j$ obtém um ponto de batalha somente se $s_j$ divide $s_i$).

Depois que todas as lutas forem concluídas, Mole faz o ranking. Uma formiga, com $v_i$ pontos de batalha obtidos, será liberada somente se $v_i = r - l$, ou seja, somente se tiver um ponto em todas as lutas que participou. Depois disso, Mole come o resto das formigas. Observe que pode haver muitas formigas liberadas ou mesmo nenhuma.

Entrada

A primeira linha contém um número inteiro $n$ ($1 \leq n \leq 10^5$), o tamanho da colônia de formigas.

A segunda linha contém $n$ números inteiros $s_1$, $s_2$, ..., $s_n$ ($1 \leq s_i \leq 10^9$), as forças das formigas.

A terceira linha contém um número inteiro $t$ ($1 \leq t \leq 10^5$), o número de casos de teste.

Cada uma das próximas $t$ linhas contém dois números inteiros $l_i$ e $r_i$ ($1 \leq l_i \leq r_i \leq n$), descrevendo uma consulta.

Saída

Imprima $t$ linhas. A $i$-ésima linha contém o número de formigas que Mole come no segmento [$l_i, r_i$].

Exemplos

ENTRADA	SAÍDA
5 1 3 2 4 2 4 1 5 2 5 3 5 4 5	4 4 1 1

Enviar solução: codeforces