XXVI Olimpíada Brasileira de Informática
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 |
