Informática - Nivel Avançado - Semana 13

Queries em Vetor

É dado um vetor A com n inteiros positivos, todos menores ou iguais a n.

Você deve processar q queries. Uma query é representada por dois números, p e k. Várias operações são realizadas em uma query; cada operação muda o valor de p para p + A_p + k. As operações são aplicadas até que p se torne maior que n. A resposta de uma query é o número de operações realizadas.

Entrada:

A primeira linha contém um inteiro, n.

A segunda linha contém n inteiros, os elementos de A.

A terceira linha contém o inteiro q.

As próximas q linhas contém dois inteiros, p e k, representando uma query.

Saída

Imprima q inteiros, a resposta para cada uma das queries.

Restrições:

  • 1 \leq n \leq 10^5
  • 1 \leq A_i \leq n
  • 1 \leq q \leq 10^5
  • 1 \leq p, k \leq n

Exemplo:

Entrada Saida
3
1 1 1
3
1 1
2 1
3 1
2
1
1

Clique aqui para submeter a sua solução.