Državno natjecanje 2016. godine za 1. i 2. razred Srednje Škole - 3. zadatak - 1. dan

Površina zatvorskog planeta Salusa Secundus je podijeljena u polja kvadratnoga oblika organiziranih u 109 redaka i 10^9 stupaca. Redci su označeni brojevima od 1 do 10^9 odozgo prema dolje, a stupci brojevima od 1 do 10^9 slijeva nadesno. Na planetu se nalazi n stražarskih tornjeva, svaki u sredini nekog polja.

Za polje P u retku r i stupcu s, područje gore-lijevo od P se sastoji od svih polja kojima je redak manji od r te stupac manji od s. Analogno definiramo područja gore-desno, dolje-lijevo i dolje-desno. Primijetite da niti jedno od ta četiri područja ne sadrži polja u retku r niti polja u stupcu s. Za polje P kažemo da je zaštićeno ako se u svakom od područja gore-lijevo, gore-desno, dolje-lijevo i dolje-desno nalazi barem jedan stražarski toranj.

Zadane su lokacije svih stražarskih tornjeva, odredite ukupni broj zaštićenih polja.

ULAZNI PODACI

U prvom redu nalazi se prirodni broj n (n ≤ 200 000) – broj stražarskih tornjeva. U k-tom od sljedećih n redova nalaze se dva prirodna broja rk i sk (rk, sk ≤ 10^9 ) – redak i stupac k-tog tornja. Niti jedna dva tornja se neće nalaziti na istom polju.

IZLAZNI PODACI

Ispišite traženi ukupni broj zaštićenih polja.

PRIMJERI TEST PODATAKA

ulaz

7
1 1
5 9
4 3
5 6
3 7
5 1
2 8

izlaz

12

ulaz

6
6 1
3 1
6 5
1 2
2 5
4 3

izlaz

8

ulaz

13
4 2
1 10
9 1
7 4
10 3
8 8
10 6
11 15
1 5
4 11
5 13
9 16
6 16

izlaz

67