Arco e flecha
O comitê olímpico está testando uma nova forma de pontuar as competições de arco e flecha, baseada em penalidades. O atleta vai atirar N flechas no alvo, em sequência. A penalidade da K-ésima flecha atirada é computada imediatamente após ela atingir o alvo, antes do próximo lançamento, e é igual ao número de flechas que estão no alvo naquele momento cuja distância ao centro do alvo é menor ou igual à distância da K-ésima flecha ao centro, excluindo a própria K-ésima flecha. Quer dizer, a penalidade é o número das K-1 flechas lançadas antes da K-ésima flecha que estão mais próximas ou à mesma distância do centro do alvo, comparadas com a K-ésima flecha. A penalidade total é a soma das penalidades das N flechas. Ganha o atleta que tiver a menor penalidade total ao final. Veja que a penalidade total pode ser zero, se o atleta for bom o bastante para acertar numa sequência estritamente decrescente de distâncias ao centro do alvo.
Entrada
A primeira linha da entrada contém um inteiro N, representando a quantidade de flechas lançadas. Cada uma das N linhas seguintes contém dois inteiros, X e Y, indicando as coordenadas do ponto em que cada flecha atingiu o alvo, definindo a sequência de lançamentos.Saída
Imprima uma linha contendo um inteiro representando a penalidade total do atleta.Restrições
- 1 ≤ N ≤ 105
- -106 ≤ X,Y ≤ 106
Informações sobre a pontuação
- Em um conjunto de testes somando 20 pontos, N ≤ 104
Exemplos
Entrada
2 1 3 5 4 |
Saída
1 |
Entrada
4 -100 85 -25 -60 18 33 0 0 |
Saída
0 |
Entrada
6 1 1 2 2 2 2 3 3 3 3 3 3 |
Saída
15 |
