Cabos Cruzados com Pesos
Em uma mesa circular existem 2n pontos distintos na borda, numerados pela ordem em que aparecem no sentido horário. Cada um dos n cabos conecta os dois pontos com o mesmo rótulo; cada rótulo aparece exatamente duas vezes. Os cabos são segmentos de reta dentro do círculo. Cada cabo i possui peso wi.
O incômodo de um cabo é a soma dos pesos de todos os outros cabos que o cruzam em um ponto interior a ambos. Cabos que apenas compartilhassem extremidades não contariam como cruzamento, mas isso não ocorre aqui porque todos os pontos da borda são distintos.
Encontre o cabo com maior incômodo. Em caso de empate, escolha o menor rótulo. Informe seu rótulo e incômodo.
Input
A primeira linha contém n. A segunda contém n pesos w1, ..., wn. A terceira contém 2n rótulos, na ordem circular, cada rótulo de 1 a n exatamente duas vezes.
Restrições:
1 ≤ n ≤ 200000; 0 ≤ wi ≤ 10^9. A resposta cabe em inteiro de 64 bits.
Output
Imprima rotulo incomodo do cabo escolhido.
Samples
Sample 1
Input
3 5 2 7 1 2 1 3 2 3
Output
2 12
O cabo 1 cruza apenas o 2, e o cabo 3 também cruza apenas o 2. O cabo 2 cruza os cabos 1 e 3, somando peso 12.