Državno natjecanje iz informatike 2016. / Druga podskupina (3. i 4. razred) – Prvi dan natjecanja - 3. zadatak

Površina zatvorskog planeta Salusa Secundus je podijeljena u polja kvadratnoga oblika organiziranih u 109 redaka i 109 stupaca.

Redci su označeni brojevima od 1 do 109 odozgo prema dolje, a stupci brojevima od 1 do 109 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.

Pronađite veličinu najveće kvadratne regije koja se sastoji samo od zaštićenih polja.

Kvadratna regija veličine m se definira kao presjek m uzastopnih redaka i m uzastopnih stupaca.

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 ≤ 109 ) – redak i stupac k-tog tornja.

Niti jedna dva tornja se neće nalaziti na istom polju.

Izlazni podaci

Ispišite traženu veličinu najveće kvadratne regije.

Primjer zadatka

Ulaz

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

Izlaz

2

Objašnjenje