Problema A - Dubai

A mais importante cidade dos Emirados Arabes Unidos, o Dubai, sofreu nos últimos anos uma enorme transformação, passando de um aglomerado populacional quase perdido no meio do deserto para uma imensa metrópople recheada dos mais fantásticos arranha-céus. Ao longo da sua principal avenida multiplicam-se as construções em altura, como o incrível Burj Dubai, que ao ficar completo no final de 2009 se tornará no mais alto edíficio do mundo, passando os 800m e batendo por larga margem todos os antigos recordes.

Os edíficios são identificados pelo seu número de ordem, contado a partir do início da avenida. Quando uma foto é tirada, apenas uma parte dos edifícios da avenida aparece na imagem e desse modo um edifício se destaca por ser o mais alto nessa mesma imagem. Por exemplo, podíamos ter os seguintes 10 edifícios ao longo da avenida:

Nº ordem:   1   2   3   4   5   6   7   8   9  10
  Altura: 350 150 200 400 831 450 200 350 100 350

Se uma foto apanhar todos os edifícios, o mais alto é o de altura 831. Se a foto apenas apanhar do primeiro ao quarto edifício, o mais alto mede 400. Já se considerarmos apenas do sétimo ao décimo edifício, existem dois empatados medindo o máximo de 350.

Dada a configuração dos edifícios ao longo da avenida, terás de descobrir qual o mais alto de cada uma duma série de fotografias.

O Problema

Dada um conjunto de N números inteiros indicando as alturas dos edifícios ao longo da avenida e F fotos, cada uma descrita por dois números A_i e B_i, indicando que a foto apanha todos os edifícios entre A_i e B_i (inclusive), a tua tarefa é descobrir qual (ou quais) o(s) edifício(s) mais alto(s) de cada foto.

Input

Na primeira linha do input vem um único número inteiro N indicando o número de edifícios da avenida (1≤N≤50 000). Segue-se uma linha contendo exactamente N inteiros E_i separados por espaços únicos, indicando as alturas dos edifícios ao longo da avenida, da esquerda para a direita (1≤E_i≤100 000 000).

Na terceira linha vem um único inteiro F indicando o número de fotos a considerar (1≤F≤50 000). Seguem-se exactamente F linhas, cada uma contendo dois números inteiros A_i e B_i, separados por um espaço, indicando que a foto apanha todos os edifícios consecutivos desde o edifício nº A_i até o edifício nº B_i ,inclusive (1≤A_i≤ B_i≤N). Nota que os edifícios são contados da esquerda para a direita, ou seja, o primeiro edifício corresponde ao edifício mais à esquerda.

Output

O output deve ser constituído exactamente por F linhas, cada uma descrevendo o(s) edifícios(s) mais alto(s) de cada foto, pela mesma ordem em que as fotos aparecem no input.

Cada uma destas linhas começa por um único inteiro indicando a altura do(s) edifício(s) mais alto. Segue-se um único espaço, seguido dos números de ordem dos edifícios da foto que têm essa altura máxima. Estes números devem também vir separados por um único espaço. Nota que se existir um único edifício de altura máxima, apenas deves imprimir esse número. Caso existam vários empatados, deves imprimir todos pela ordem em que aparecem na avenida (isto é, da esquerda para a direita). É garantido que no máximo existem 50 edifícios empatados com a altura máxima.

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 50% dos pontos, o número de prédios e de fotos é inferior ou igual a 200.

Exemplo de Input

10
350 150 200 400 831 450 200 350 100 350
3
1 10
1 4
7 10

Exemplo de Output

831 5
400 4
350 8 10