Tacos de bilhar
Jogos de bilhar, em que tacos são usados para arremessar uma bola contra outras em uma mesa, têm muitas variantes, como sinunca, mata-mata, bilhar francês e outras. São muito antigos, havendo relatos sobre jogos similares desde 1340. O Sr. Jorge é um renomado artesão que fabrica tacos de bilhar sob encomenda. Jogadores de todo o mundo procuram o Sr. Jorge, para confeccionar tacos nos mais diversos comprimentos, pois seus tacos são perfeitos, bem balanceados e muito bonitos. Cada vez que um cliente pede um taco de um dado comprimento, o Sr. Jorge primeiro verifica se ele tem um taco com esse comprimento no estoque. Se tem, ele envia o taco para o cliente. Se não tem, ele faz duas cópias do taco, envia uma para o cliente e guarda a outra no estoque. Assim, ele nunca tem no estoque mais do que um taco com um determinado comprimento. O estoque do Sr. Jorge está muito grande, e ele tem perdido muito tempo procurando por tacos. Ele pensa em usar um sistema computadorizado para manter o seu estoque de tacos, e precisa de sua ajuda. Dadas as consultas ao estoque calcule o número total de tacos fabricados, supondo que inicialmente o estoque esteja vazio..Entrada
A primeira linha da entrada contém um inteiro C que indica o número de consultas ao estoque. A segunda linha contém C números inteiros, indicando as consultas ao estoque. Cada valor de consulta indica o comprimento de um taco desejado. As consultas são dadas na entrada na ordem em que o Sr. Jorge as executa. Assuma que o estoque está vazio inicialmente.Saída
Seu programa deverá imprimir um único número, o número de tacos fabricados.Restrições
- 1 ≤ C ≤ 10^5
- 1 ≤ comprimento dos tacos ≤ 10^6
Informações sobre a pontuação
- Em um conjunto de casos de teste equivalente a 40 pontos, C ≤ 1000.
Exemplos
Entrada
4 80 100 80 50 |
Saída
6 |
Entrada
1 1000 |
Saída
2 |
Volta ao início