E. Dreamoon ба Notepad

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

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

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

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

Dreamoon notepad.exe-г ашиглан хэцүү асуудалтай нэгэн баримт үүсгэсэн. Энэ баримт нь $n$ мөр текст, $a_{i}$ нь $i$-р мөрийн уртыг илэрхийлнэ. Тэр одоо заагчаа хамгийн хурдан шилжүүлэх арга замыг олохыг хүсэж байгаа, учир нь түүний баримт хэтэрхий урт юм.

Одоо заагч $(r, c)$ байрлалд байгаа ба $r$ нь мөрийн дугаар, $c$ нь тухайн мөрөнд байгаа заагчийн байрлал. Бидэнд $1 ≤ r ≤ n$ ба $0 ≤ c ≤ a_{r}$ байна.

Одоо заагч $(r, c)$ байрлалд байгаа гэж үзвэл notepad.exe-д дараах зургаан үйлдлээр заагчаа шилжүүлж чадна:

  1. дээшээ товч: заагчийн шинэ байрлал $(nr, nc) = (max(r - 1, 1), min(a_{nr}, c))$
  2. доошоо товч: заагчийн шинэ байрлал $(nr, nc) = (min(r + 1, n), min(a_{nr}, c))$
  3. зүүн товч: заагчийн шинэ байрлал $(nr, nc) = (r, max(0, c - 1))$
  4. баруун товч: заагчийн шинэ байрлал $(nr, nc) = (r, min(a_{nr}, c + 1))$
  5. буцах товч: заагчийн шинэ байрлал $(nr, nc) = (r, 0)$
  6. дуусгах товч: заагчийн шинэ байрлал $(nr, nc) = (r, a_{r})$

Чамд Dreamoon-ий $q$ асуулт мөн оролтын тодорхойлолт өгөгдсөн ($n$ ба $a_{i}$ дараалал). Асуулт бүр нь заагч $(r_{1}, c_{1})$-ээс $(r_{2}, c_{2})$-луу шилжихэд хэрэгтэй хамгийн бага товчны даралтын тоог асууна.

Оролт

Эхний мөрөнд текстийн мөрийн тоо $n(1 ≤ n ≤ 400, 000)$ бүхэл тоо байна.

Дараагийн мөрөнд $n$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{n}(1 ≤ a_{i} ≤ 10^{8})$ байна.

Гуравдугаар мөрөнд бүхэл тоо $q(1 ≤ q ≤ 400, 000)$ байна.

Дараагийн $q$ мөр бүр нь асуултыг төлөөлсөн дөрвөн бүхэл тоог агуулна. $r_{1}, c_{1}, r_{2}, c_{2}$ ($1 ≤ r_{1}, r_{2} ≤ n, 0 ≤ c_{1} ≤ a_{r1}, 0 ≤ c_{2} ≤ a_{r2}$).

Гаралт

Асуулт бүрийн үр дүнг хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
9
1 3 5 3 1 3 5 3 1
4
3 5 3 1
3 3 7 3
1 0 3 3
6 0 7 3
Гаралт
2
5
3
2
Оролт
2
10 5
1
1 0 1 5
Гаралт
3

Тэмдэглэл

Эхний жишээнд, нэгдүгээр асуултыг дараах товчнуудаар шийдэж чадна: буцах, баруун.

Хоёрдугаар асуултыг дараах товчнуудаар шийдэж чадна: доошоо, доошоо, доошоо, буцах, доошоо.

Гуравдугаар асуултыг дараах товчнуудаар шийдэж чадна: доошоо, буцах, доошоо.

Дөрөвдүгээр асуултыг дараах товчнуудаар шийдэж чадна: буцах, доошоо.

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