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