Colônia de Formigas
Mole é um tamanduá, e está com muita fome. Ele encontrou uma colônia de formigas, composta por formigas, ordenadas em sequência. Cada formiga tem uma força .
Para tornar seu jantar mais interessante, Mole organiza uma versão dos «Jogos Vorazes» para as formigas. Ele escolhe dois números e e cada par de formigas com índices entre e (inclusive) lutará. Quando duas formigas e lutam, a formiga obtém um ponto de batalha apenas se divide (também, formiga obtém um ponto de batalha somente se divide ).
Depois que todas as lutas forem concluídas, Mole faz o ranking. Uma formiga, com pontos de batalha obtidos, será liberada somente se , 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 (), o tamanho da colônia de formigas.
A segunda linha contém números inteiros , , ..., (), as forças das formigas.
A terceira linha contém um número inteiro (), o número de casos de teste.
Cada uma das próximas linhas contém dois números inteiros e (), descrevendo uma consulta.
Saída
Imprima linhas. A -ésima linha contém o número de formigas que Mole come no segmento [].
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