F. Пуддинг Мангас

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Энэ бодлогонд та Пуддинг Мангас тоглоомын хялбарчилсан хувилбартай таарна.

Аль ч төрлийн тоглоомыг хөгжүүлэхэд хамгийн чухал ажил бол үе шат бүтээх юм. Пуддинг Мангас тоглоомын талбай нь $n × n$ шатрын хөлөг шиг том талбай байх бөгөөд талбай дээр $n$ ширхэг нүдэн дээр мангас болон обьектууд байгаа. 2 мангас бие биеэндээ хүрвэл тэд хоорондоо наалдан нэг том мангас болон хувирдаг (Пуддинг шиг санаж байна уу?).

Хэрвээ анхандаа мөр болон багана болгонд нэг мангас байх бөгөөд бусад обьектуудыг зөв нүдэнд байрлуулсан байвал тухайн талбайг сонирхолтой гэж үздэг.

Тоглоомын хөгжүүлэлтийг илүү ашигтай болгохын тулд ашигладаг арга нь ашиглаж болохуйц нөөцийг дахин ашиглах юм. Жишээ нь, хэрвээ $n × n$ том талбай байвал том талбайтай ижил нөхцөлтэйгөөр яг $k$ ширхэг мангас байхаар энэ дотор $k × k$ квадрат хэсэг сонгон авч болно.

Та том талбайд яг $k$ ширхэг мангас байхаар хэдэн ширхэг $k × k$ ($1 ≤ k ≤ n$) квадрат хэсэг байгааг олохыг хүсч байгаа. Энэхүү тоог олно уу.

Оролт

Эхний мөрөнд том талбайн хэмжээ болох нэг бүхэл тоо $n$ ($1 ≤ n ≤ 3 × 10^{5}$) өгөгдөнө.

Дараагийн $n$ ширхэг мөрөнд мангаснуудын анхны координатууд өгөгдөнө. $i$ дэхь мөрөнд $i$ дэхь мангасны нүдний мөрийн дугаар болон багананы дугаар болох 2 тоонууд $r_{i}, c_{i}$ ($1 ≤ r_{i}, c_{i} ≤ n$) өгөгдөнө.

Энд бүх мөрний дугаарууд $r_{i}$ нь хоорондоо ялгаатай ба бүх багананы дугаарууд $c_{i}$ нь ч гэсэн хоорондоо ялгаатай.

Гаралт

Том талбайд нийт хэдэн ширхэг ялгаатай квадрат хэсэг байгааг олж энэ тоог хэвлэнэ үү. Энд квадрат хэсэг болгон том талбайтай адилхан нөхцлийг хангах ёстой гэдгийг санана уу.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
5
1 1
4 3
3 2
2 4
5 5
Гаралт
10
Сэтгэгдлүүдийг ачааллаж байна...