Um grupo de
amigos está a fazer uma enorme colecção de cromos. Os cromos são
identificados por um número inteiro e podem desse modo ser
distinguidos entre si. Como é complicado (e muito caro!) um único
amigo conseguir ter a colecção toda, decidiram juntar esforços e criar
uma única colecção com todos os cromos que entre eles detenham.
Para ajudar a perceber os cromos que cada um tem, os amigos decidiram pegar individualmente nos seus cromos e colocá-los por ordem. Como muitas vezes apareciam vários números consecutivos, decidiram anotar apenas intervalos de números. Por exemplo, uma colecção entre amigos podia ser assim descrita:
Amigo 1: [1,6] e [12,15], ou seja, os cromos 1, 2, 3, 4, 5, 6, 12, 13, 14 e 15. Amigo 2: [6,9], ou seja, os cromos 6, 7, 8 e 9. Amigo 3: [3,8], ou seja, os cromos 3, 4, 5, 6, 7, 8.
Como o grupo tem vários amigos, os intervalos de cada um são diferentes e podem ter intersecções uns com os outros, que correspondem a cromos repetidos. Sabendo isso, o que eles querem mesmo saber é quantos cromos diferentes (não repetidos) eles têm. No exemplo atrás descrito teriam precisamente 13 cromos diferentes, nomeadamente os cromos 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14 e 15.
Para um caso geral, será que podes ajudar os amigos a saberem quantos cromos diferentes têm?
Dado um conjunto arbitrário de intervalos de números, representando os cromos, a tua tarefa é dizer quantos são os cromos diferentes, ou seja, quantos números diferentes aparecem nos intervalos.
Na primeira linha do input vem um número inteiro I indicando o número de intervalos a considerar. Seguem-se exactamente I linhas, cada uma contendo dois números INFi e SUPi, separados por um único espaço, representando respectivamente o limite inferior e superior do intervalo. Nota que o intervalo inclui os cromos nos limites. Por exemplo, o intervalo [1,3] inclui o 1 e o 3, para além do 2.
Os intervalos podem vir por qualquer ordem e podem ter um qualquer número de intersecções. Nota também que os intervalos podem pertencer a um qualquer número de amigos..
O output deve ter exactamente uma linha, contendo um único inteiro indicando o número de cromos diferentes no conjunto de todos os intervalos dados.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ I ≤ 100 000 | Número de intervalos | |
| 1 ≤ INFi ≤ SUPi ≤ 2 000 000 000 | Números possíveis dos cromos |
Para um conjunto de casos de teste valendo 40% dos pontos, o número de intervalos será inferior a 100 e os números dos cromos serão inferiores a 1 000 000.
4 1 6 12 15 6 9 3 8
13