D. Агаарын шугам

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

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

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

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

Вася ойролцоох ойн моднууд дээр агаарын шугам татахаар шийдсэн. Тэр шугамыг боломжит хамгийн урт байлгахыг хүсч байгаа боловч ойд байгаа бүх модны өндрийг яг сайн санахгүй байгаа. Тэр бүх модны нэгээс нь бусдынх нь зөв өндрийг санаж байгаа гэдэгтээ итгэлтэй байна.

Ой мөрийн дагуу байрласан $n$ модоос бүрдэх ба зүүнээсээ баруун тийш $1$-c $n$ хүртэл дугаарлагдсан. Васягийнхаар бол $i$-р модны өндөр нь $h_{i}$ байна. Агаарын шугамын урт $k$ нь $i_{1}, i_{2}, ..., i_{k}$ ($i_{1} < i_{2} < ... < i_{k}$) байх $k$ ($1 ≤ k ≤ n$) ширхэг модоор үргэлжлэх ёстой буюу моднуудын өндөр нь өсөх дараалалтай буюу $h_{i_{1}} < h_{i_{2}} < ... < h_{i_{k}}$ байх ёстой.

Петя уг ойд Васятай хамт байсан ба одоо тэр Васягийн $h$ дарааллын алдааны тухай $q$ таамаглалтай байгаа. Түүний $i$-р таамаглал нь хоёр бүхэл тоон утга $a_{i}$ ба $b_{i}$-с бүрдэх ба Петягийнхаар бол $a_{i}$ дугаартай модны өндөр нь үнэндээ $b_{i}$-тай тэнцүү байсан гэдгийг илтгэнэ. Петягийн таамаглалууд нэг нэгнээсээ бие даасан байна.

Таны ажил бол $q$ таамаглал бүрийн хувьд моднуудын дээгүүр баригдах агаарын шугамын хамгийн урт уртыг олох юм.

Энэ бодлогод агаарын шугамын уртыг агаарын шугамыг бүрдүүлж байгаа моднуудын тоотой тэнцүү гэж үзнэ.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n, m ≤ 400 000$) байх ба харгалзан ойд байгаа моднуудын тоо болон Петягийн таамаглалуудын тоо.

Дараагийн мөрөнд $n$ бүхэл тоон утга $h_{i}$ ($1 ≤ h_{i} ≤ 10^{9}$) байх ба Васягийнхаар моднуудын өндөр байна.

Дараагийн $m$ мөр бүрт хоёр бүхэл тоон утга $a_{i}$ ба $b_{i}$ ($1 ≤ a_{i} ≤ n$, $1 ≤ b_{i} ≤ 10^{9}$) байна.

Гаралт

Петягийн таамаглал бүрийн хувьд нэг ширхэг бүхэл тоон утгыг хэвлэх ба энэ нь уг таамаглалын дор барьж болох агаарын шугамын хамгийн урт уртыг илэрхийлнэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
4 4
1 2 3 4
1 1
1 4
4 3
4 5
Гаралт
4
3
3
4
Оролт
4 2
1 3 2 6
3 5
2 4
Гаралт
4
3

Тэмдэглэл

Эхний жишээг авч үзье. Эхний таамаглал үнэндээ Васягийн санаж буй өндөртэй таарч байна. Хоёр дахь таамаглалд моднуудын өндөр нь $(4, 2, 3, 4)$ байх ба гуравдугаар таамаглалд $(1, 2, 3, 3)$ байна харин дөрөвдүгээр таамаглалд $(1, 2, 3, 5)$ байна.

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