SPOJ Brasil

Autor: Vinicius Ruoso

A Seleção Brasileira passou por maus momentos durante a Copa do Mundo disputada em seu país. A preocupação entre a comissão técnica foi tão grande que agora estão investindo em análise de dados para verificar como é possível melhorar o time.

A equipe de estatísticos da seleção descobriu que o minuto em que os gols ocorrem nas partidas é uma variável importante. Além disso, um número ainda mais importante para eles é a mediana destes valores. Para realizar uma análise de todos os jogos da seleção, eles agregaram os gols de vários jogos em uma sequência. Por exemplo, se no jogo 1 ocorreu um gol aos 85 minutos (e não houve prorrogação) e no jogo 2 ocorreu um gol aos 5 minutos, os números de interesse são 85 e 95.

Os estatísticos não são muito bons com programação e pediram a sua ajuda para determinar os números que eles precisam. Para cada um dos N gols contabilizados, eles estão pedindo que você calcule a mediana dos minutos de todos os gols que foram contabilizados até ele. Em outras palavras, para todo gol i (1 ≤ i ≤ N), calcular a mediana dos minutos em que os gols [g₁, g₂, ..., g_i] ocorreram. Para facilitar a interpretação dos dados, retorne a soma destas medianas módulo 1000000007 (10⁹+7). Como eles não tiveram tempo para organizar os números, os gols podem não ter sido contabilizados na mesma ordem em que ocorreram.

Lembrando que a definição de mediana utilizada é a seguinte: a mediana de uma sequencia de n números é o valor na sequência, quando ordenada, da posição (n+1)/2 quando n é impar, ou o valor da posição n/2 quando n é par (considera-se a sequência 1-indexada). Por exemplo, a mediana da sequência [1, 2, 3, 4, 5] é 3, enquanto da sequência [1, 2, 3, 4, 5, 6, 7, 8] é 4.

Entrada

A entrada inicia com uma linha contendo um inteiro N (1 ≤ N ≤ 10⁶) indicando o número de gols que foram contabilizados. As próximas N linhas contém a descrição dos gols contabilizados. A linha i (1 ≤ i ≤ N) contém um inteiro g_i (1 ≤ g_i ≤ 10⁹) descrevendo o instante de tempo em que o gol i ocorreu.

Saída

Imprima uma linha contendo o número de interesse dos estatísticos.

Examplo

Entrada:
8
11
23
24
26
29
69
79
90

Saída:
168