que estão no segmento do
liº ao
riº elemento".< /div>
Uma subsequência da sequência a1 , ..., an< /sub> é uma sequência que pode ser obtida removendo vários elementos ai (a ordem relativa dos
restantes
Os elementos
não podem ser alterados). Então, por exemplo, a sequência (2, 4) é uma subsequência da sequência (1, 2, 3, 4, 5) (você pode deletar os elementos 1, 3 e 5 ), e a sequência ( 5, 1) não é.< br />
Entrada
A primeira linha contém um inteiro
n (1 <= n <= 3000 ) é o número de elementos na sequência. A segunda linha contém
n< /code> Números separados por espaços são os elementos da sequência. Todos os elementos não excedem 109 em valor absoluto. A terceira linha contém um único inteiro q< /code> (1 < ;= q <= 105) - número de solicitações. As seguintes linhas q descrevem as consultas. Descrição da consulta i -th - dois números li e rj (1 <= li <= ri <= n) , separados por espaços.
Saída dados
Números Saída q - respostas para consultas. Os números devem ser exibidos um por linha na mesma ordem em que as consultas são descritas na entrada.
Exemplos
| # |
Entrada |
Saída |
| 1 |
6
3 3 -5 7 4 9
6
14
1 2
23
15
3 5
25 |
2
1
1
2
2
2 |