Zadanie

Cenná remíza

Počet bodov: 20

Janka si nedala poradiť životnými skúsenosťami a chce si kúpiť nový Macbook.

Nový Macbook však stojí veľa dukátov, a na tie sa ťažko robí. Ľahšie ako práca je si staviť na dobrý futbalový zápas medzi KSP (Klub Silné Pecky) a FKS (Futbalový Klub Slovakistanu). Keďže tieto týmy sú celkom vyrovnané, Janka si vsadila na to, že bude remíza.

Vždy keď zápase nastane remíza, Janka má štastný moment. Vy ste ten zápas až tak dobre nesledovali – \(n\) krát ste si pozreli, aký je momentálny stav. Zistite, koľko najviac šťastných momentov mohla Janka počas zápasu zažiť.

Úloha

Zápas sa začal skóre 0:0. Potom máte \(n\) chronologických záznamov, aké bolo vo futbalovom zápase skóre. Posledný záznam je finálne skóre. Zistite, koľko najviac krát mohla byť počas zápasu remíza, teda skóre \(x\):\(x\) pre nejaké \(x\).

Vstup a Výstup

V prvom riadku je číslo \(n\) - počet krát čo ste sa pozreli na skóre.

V každom z \(n\) nasledujúcich riadkov sú dve čísla \(a_i\), \(b_i\), označujúc že skóre bolo \(a_i\):\(b_i\). Tento zoznam je korektný, teda ak \(x < y\) tak \(a_x \leq a_y\) a \(b_x \leq b_y\).

Vypíšte jedno číslo - koľko najviac krát mohla byť remíza, a teda koľko štastných momentov mohla Janka zažiť.

Platí \(1 \leq n \leq 10^6\). V prvej sade žiadny z tímov nedal viac ako \(10^6\) gólov, v druhej sade je tento limit \(10^9\).

Príklad

Input:

3
1 1
2 4
7 6

Output:

6

Napríklad mohlo byť postupne 0:0, 0:1, 1:1, 1:2, 2:2, 2:3, 2:4, 3:4, 4:4, 4:5, 5:5, 5:6, 6:6, 7:6, a v tom bolo šesť remíz. Viac ich byť nemohlo.