david113

Uma das atividades de recreação preferidas de Letícia é compor desenhos com linhas coloridas esticadas entre preguinhos numa base de madeira. Quanto mais cruzamentos entre pares de linhas, mais interessante fica a figura. Neste problema temos N pregos na vertical e N pregos na horizontal, como na figura abaixo. Os pregos na vertical possuem uma numeração fixa, de 1 a N, de baixo para cima. Os pregos na horizontal também são numerados de 1 a N, mas a ordem pode ser qualquer uma. Letícia vai sempre esticar uma linha entre cada par de pregos que tiverem o mesmo número. Dada a ordem dos pregos horizontais, seu programa deve computar o número total de cruzamentos entre pares de linhas no desenho de Letícia. Por exemplo, os três desenhos da figura possuem, respectivamente, 0, 6 e 15 cruzamentos. Entrada A primeira linha da entrada contém um número natural N. A segunda linha contém N números naturais distintos de 1 a N, representando a ordem dos pregos na horizontal. Saída Seu programa deve escrever uma linha na saída, contendo o número de cruzamentos entre pares de linhas, conforme a descrição anterior. Restrições 2 ≤ N ≤ 60000 Informações sobre a pontuação Em um conjunto de casos de teste somando 60 pontos, N ≤ 30000 Exemplos Entrada 6 1 5 3 4 6 2 Saída 6 Entrada 15 5 8 15 12 2 1 9 7 4 11 14 10 3 6 13 Saída 49