E. Хашаан дээрх тэмдэг

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

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

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

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

Бизон аварга өөрийн хашаагаа саяхан будаж дууссан. Энэ хашаа нь дурын өндөртэй, $1$ метр өргөнтэй $n$ хавтангуудын дарааллаас бүрдэнэ. $i$-р хавтангын өндөр нь $h_{i}$ метр байна. Мөн зэргэлдээх хавтангуудын хооронд ямар ч завсаргүй байна.

Бизон хашаагаа будсаны дараа хашаан дээрээ "зарна" гэсэн тэмдэг тавихаар шийдэв. Тэмдгийг тэгш өнцөгт цаасны хэсэг дээр зурсан ба хашаан дээр байрласан байна, тэгэхээр тэмдгийн талууд нь хашааны хавтангуудтай параллель бөгөөд зарим хавтангуудын ирмэгүүдтэй нийлсэн байна. Бизон аварга тэмдгийн байрлалд дараах хязгаарлалтуудыг танилцуулсан:

  1. Тэмдгийн өргөн нь яг $w$ метр байх ёстой.
  2. Тэмдэг нь хашааны $l$-с $r$-р хавтангуудын (оролцуулаад) хэсэг дотор багтсан байх ёстой (мөн, хашаануудын босоо чиглэлийн хүрээнээс хэтэрч болохгүй).

Тэмдэг үнэхээр гоё учраас Бизон аварга тэмдгийн өндрийг аль болох их байлгахыг хүссэн.

Чамд хашааны тодорхойлолт болон тэмдгийг байрлуулах хэд хэдэн асуулт өгөгдсөн. Асуулт бүрийн хашааны харгалзах хэсгүүд дээр байрласан өгөгдсөн тогтмол өргөнтэй тэмдгийн боломжит хамгийн их өндрийг хэвлэнэ.

Оролт

Оролтын эхний мөрөнд хашааны хавтангуудын тоо болох $n$ бүхэл тоог оруулна ($1 ≤ n ≤ 10^{5}$).

Хоёр дахь мөр нь зайгаар тусгаарлагдсан $n$ ширхэг бүхэл $h_{i}$ тоонуудаас бүрдэнэ. Эдгээр нь хавтангуудын өндрүүд юм ($1 ≤ h_{i} ≤ 10^{9}$).

Гурав дахь мөр нь асуултуудын тоо болох $m$ бүхэл тоог агуулна ($1 ≤ m ≤ 10^{5}$).

Дараагийн $m$ мөрүүд нь асуултуудын тодорхойлолтыг агуулах ба асуулт бүрийг гурван бүхэл $l$, $r$, $w$ ($1 ≤ l ≤ r ≤ n$, $1 ≤ w ≤ r - l + 1$) тоонууд илэрхийлнэ. Энэ нь харгалзан хашааны хэсэг ба тэмдгийн өргөн юм.

Гаралт

Асуулт бүрийн хариултыг тусдаа мөрөнд хэвлэнэ. Энэ нь бүх нөхцлийг хангасан хашааны харгалзах хэсэгт тавьж чадах тэмдгийн хамгийн их өндөр юм.

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

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

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

Тэмдэглэл

Жишээнд тодорхойлсон хашаа дараах байдлаар харагддаг:

Бүх асуултын боломжит байрлал доор өгөгдсөн байна.

Эхний асуулт дахь тэмдгийн нийцтэй байрлал. Хоёрдугаар асуулт дахь тэмдгийн нийцтэй байрлал. Гуравдугаар асуулт дахь тэмдгийн нийцтэй байрлал.

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