D. Хашаа

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

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

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

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

Жон Дое зүүнээс баруун тийш эгнэсэн $n$ тэгш өнцөгт банзнаас тогтох муруй хашаатай: $i$-р $(1 ≤ i ≤ n)$ (зүүнээс баруун тийш) банз нь 1 өргөнтэй ба $h_{i}$ өндөртэй. Бид $i$-р $(1 ≤ i ≤ n)$ (зүүнээс баруун тийш) банзыг $i$ дугаартай гэж үзнэ.

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

Хашааны $l_{1}$-с $r_{1}$ хүртэлх болон $l_{2}$-с $r_{2}$ хүртэлх хоёр хэсэг нь дараах нөхцөлүүдийг хангаж байвал таарч байна гэнэ:

  • хэсгүүд огтлолцохгүй буюу хашааны хоёр хэсэгт зэрэг агуулагдах ямар ч банз байхгүй;
  • хэсгүүд ижил өргөнтэй байх;
  • бүх $i$-н $(0 ≤ i ≤ r_{1} - l_{1})$ хувьд дараах нөхцөл биелэх: $h_{l_{1} + i} + h_{l_{2} + i} = h_{l_{1}} + h_{l_{2}}$.

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

Оролт

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

Гурав дахь мөрөнд бүхэл тоо $q$ ($1 ≤ q ≤ 10^{5}$) байх буюу асуулгуудын тоо юм. Дараагийн $q$ мөр бүрт хоёр бүхэл тоо $l_{i}$ ба $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) байх буюу хашааны уг хэсгийн хүрээ банзнуудын дугаар юм.

Гаралт

Асуулга бүрийн хувьд өгөгдсөн хэсэгтэй таарах хашааны ялгаатай хэсгүүдийн тоог илэрхийлэх нэг бүхэл тоог хэвлэ. Асуулгуудын хариултуудыг тэдний оролтонд өгөгдсөн дарааллаар хэвлэ.

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

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

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