Banco do Faraó

Pouca gente sabe, mas foi no Antigo Egito que surgiram os primeiros bancos, de uma forma muito semelhante ao que conhecemos hoje.

O principal banco era do faraó, que decidia, de tempos em tempos, tomar para o Estado o conteúdo de algumas contas. Isso ocorria da seguinte forma. Dado $N$, o número de correntistas do Banco do Faraó (era esse o nome do banco), cada conta podia ter uma quantia em menés (moeda do Antigo Egito) que podia ser, inclusive, negativa (indicando que a pessoa devia aquela quantia ao banco), ou seja, o estado de cada conta era um inteiro ai. O objetivo do faraó era fazer diversas consultas nas contas de seus súditos. Dado um intervalo $[A,B]$ (correspondente as contas $a_A$, $a_{A+1}$, ... , $a_{B-1}$, $a_B$) o faraó desejava encontrar um subintervalo de soma máxima, ou seja, cujo sequestro pelo Estado renderia ao Faraó a maior quantia de dinheiro. Isso era explicado aos correntistas como sendo uma oferenda a Amon-Ahcid, o Deus egípcio do dinheiro.

Fazendo regularmente tais oferendas o deus ficava satisfeito e permitia que o sistema econômico funcionasse perfeitamente. Isso durou surpreendentemente mais de 500 anos, até que num desses sequestros os correntistas se rebelaram, tomaram o palácio e mataram o faraó. O banco foi saqueado e o sistema ruiu. Só se ouviu falar de bancos novamente centenas de anos depois.

Sua tarefa é dado um registro de contas e uma série de consultas, determinar para cada consulta um intervalo de soma máxima.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro $T$ indicando o número de instâncias.

A primeira linha de cada instância contém um inteiro $N$, indicando o número de contas no Banco do Faraó. A segunda linha de cada instância contém $N$ inteiros $V_i$, indicando os saldos nas contas dos correntistas. A terceira linha contém um inteiro $Q$, indicando o número de consultas que serão feitas. Cada uma das $Q$ linhas seguintes contém dois inteiros $A$ e $B$, indicando o intervalo que deve ser consultado.

Saída

Para cada instância seu programa deve produzir $Q$ linhas na saída, sendo uma para cada consulta. Cada uma dessas linhas deve conter dois inteiros: o primeiro representa a soma do intervalo com maior soma, e o segundo, o número de elementos desse intervalo. Caso haja mais de um intervalo com maior soma, imprima o número de elementos naquele com maior número de elementos.

Restrições

• $1 \leq N \leq 10^5$
• $-10^4 \leq V_i \leq 10^4$
• $1 \leq Q \leq 10^5$
• $1 \leq A,B \leq N$