E. Үнээнүүдийн теннисний тэмцээн

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

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

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

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

Фермер Жон өөрийн $n$ үнээнүүдийнхээ дунд теннисний тэмцээн зохиохоор болжээ. Үнээ бүр нь $s_{i}$ чадварын төвшинтэй ба ямар ч 2 үнээ нь ижил чадварын төвшинтэй байхгүй юм. Тэмцээн дээр үнээ бүр нь бусад үнээнүүдтэй яг нэг удаа тоглох ба үнээ бүр нь өөрөөсөө бага чадварын төвшинтэй үнээ бүрийг хожих юм.

Тэгсэн хэдий ч Фермер Жон хамгийн их эсвэл бүх тоглолтдоо хожигдох чадвар султай үнээнүүдийн хувьд уг тэмцээн нь ёс суртахуунгүй санагдана хэмээн бодсон бөгөөд тэрээр зарим тоглолтын үр дүнг солихоор болжээ. Тодруулан хэлбэл ялгаатай $k$ тохиолдлын хувьд тэрээр 2 бүхэл тоо $a_{i}, b_{i}$ $(a_{i} < b_{i})$-г сонгох ба $a_{i}$ болон $b_{i}$-ын хооронд (эдгээр нь өөрсдөө орно) байх чадварын төвшинтэй үнээнүүдийн хоорондох тоглолтуудын үр дүнг солино. Өөрөөр хэлбэл $x, y$ хос бүрийн хувьд тэрээр эцсийн онооны самбар дээрх тоглолтын үр дүнг өөрчилнө (хэрэв $x$ тоглолтод хожсон бол одоо онооны самбар дээр эсрэгээр нь $y$ уг тоглолтод хожсон гэж харуулах юм). Фермер Жон тоглолтын үр дүнг олон тооны удаа өөрчлөх боломжтой. $a_{i}$ болон $b_{i}$ нь зарим үнээнүүдийн чадварын төвшинтэй тэнцүү байна.

Фермер Жон тэмцээний үр дүнг харан уг тэмцээн нь хэр тэнцвэртэй болж өнгөрснийг тодорхойлохыг хүсжээ. Тодруулан хэлбэл тэрээр эцсийн онооны самбар дээр үзүүлснээр $p$ үнээ нь $q$ үнээг хожсон, $q$ үнээ нь $r$ үнээг хожсон ба $r$ үнээ нь $p$ үнээг хожсон байх $(p, q, r)$ үнээнүүдийн гурвалын тоог тоолохыг хүсжээ. Түүнд уг тоог тодорхойлж өгнө үү.

Хэрэв 2 ширхэг үнээнүүдийн гурвал нь ижил үнээнүүдийн олонлог агуулаагүй байвал (ө.х нэг гурвал дотор байх бөгөөд нөгөө гурвалд нь байхгүй байх нэг үнээ оршин байна) уг 2 гурвалыг ялгаатай гэж үзэхийг анхаарна уу.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $n$ болон $k$ $(3 ≤ n ≤ 10^{5}; 0 ≤ k ≤ 10^{5})$ өгөгдөнө. Дараагийн мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг ялгаатай бүхэл тоо $s_{1}, s_{2}, ..., s_{n}$ $(1 ≤ s_{i} ≤ 10^{9})$ өгөгдөх ба эдгээр нь үнээнүүдийн чадварын төвшнүүдийг илэрхийлнэ. Дараагийн $k$ мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $a_{i}$ болон $b_{i}$ $(1 ≤ a_{i} < b_{i} ≤ 10^{9})$ өгөгдөх ба эдгээр нь Фермер Жон-ын онооны самбарт хийх өөрчлөлтүүдийг илэрхийлнэ.

Гаралт

Эцсийн онооны самбар дээр үзүүлснээр $p$ үнээ нь $q$ үнээг хожсон, $q$ үнээ нь $r$ үнээг хожсон ба $r$ үнээ нь $p$ үнээг хожсон байх $(p, q, r)$ үнээнүүдийн гурвалын тоо болох ганц бүхэл тоог хэвлэнэ үү.

С++ дээр 64-битийн бүхэл тоонуудыг унших эсвэл бичихдээ %lld тодорхойлогчийг битгий ашиглана уу. cin, cout streams эсвэл %I64d тодорхойлогчийг ашиглахыг илүүд үзнэ үү.

Орчуулсан: Баатархүү

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

Оролт
3 2
1 2 3
1 2
2 3
Гаралт
1
Оролт
5 3
5 9 4 1 7
1 7
2 8
3 9
Гаралт
3

Тэмдэглэл

Эхний жишээнд үнээ 3 > үнээ 1, үнээ 3 > үнээ 2, ба үнээ 2 > үнээ 1 байна. Тэгсэн хэдий ч үнээ 1 болон 2, үнээ 2 болон 3-ын хоорондох тоглолтуудын үр дүн солигдсон ба одоо эцсийн онооны самбар нь үнээ 1 > үнээ 2, үнээ 2 > үнээ 3, болон үнээ 3 > үнээ 1 гэж харуулна. Иймд үнээ 1, 2 болон 3 нь тэнцвэртэй гурвал үүсгэх юм.

Сэтгэгдлүүдийг ачааллаж байна...