Les vaches passent l’été près de Front Range dans les Rocky Mountains, non loin de la maison de Coach Rob. On voit $N$ montagnes ($N \le 100{,}000$) à l’horizon, par exemple (ici $N=5$) :

                   /\
      /\          /  \  /\
     /  \/\    /\/    \/  \
    /    \ \  /  \    /    \
  -----------------------------

Chaque montagne est un triangle isocèle dont la hauteur vaut exactement deux fois la longueur de la base. On donne les coordonnées $x$ des deux extrémités de sa base ; ce sont des entiers positifs représentables sur 16 bits signés. Calculez l’aire totale de l’union de ces montagnes.

Entrée

• Ligne 1 : entier $N$.
• Lignes $2..N+1$ : chaque ligne décrit une montagne par deux entiers triés et séparés par un espace.

Sortie

Un entier donnant l’aire de l’union des montagnes. Cette aire est toujours entière et représentable sur 32 bits signés.

Exemples

Entrée 1

5
2 7
6 9
12 15
14 21
20 25

Sortie 1

114

Auteur du problème : Brian Dean, 2001