F. Шоргоолжны колони

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

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

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

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

Сохор номин дахиад л өлсжээ. Тэр дараалан байрласан $n$ шоргоолжтой шоргоолжны колони олов. $i$ ($1 ≤ i ≤ n$) шоргоолж бүр $s_{i}$ хүчтэй.

Сохор номин оройн хоолоо илүү сонирхолтой болгохын тулд, шоргоолжнуудад «Өлсгөлөн тоглоом»-ийн хувилбарыг зохион байгуулж байна. Тэр $l$, $r$ ($1 ≤ l ≤ r ≤ n$) хоёр тоо сонгосон ба $l$, $r$ (оролцуулаад)-ийн хоорондох индекстэй хос шоргоолж бүр тулалдана. $i$ ба $j$ шоргоолж тулалдсан үед хэрэв $s_{i}$ нь $s_{j}$-д хуваагддаг бол шоргоолж $i$ байлдааны нэг оноо авна.(мөн $s_{j}$ нь $s_{i}$-д хуваагддаг бол шоргоолж $j$ байлдааны нэг оноо авна).

Бүх тулаан дууссаны дараа, сохор номин зэрэглэл тогтооно. Шоргоолж $i$ нь $v_{i}$ байлдааны оноотой ба $v_{i} = r - l$ бол, өөрөөр хэлбэл оролцсон тулаан бүрээсээ оноо авсан бол түүнийг суллана. Дараа нь үлдсэн шоргоолжийг идэхээр болов. Олон шоргоолж суллагдаж, эсвэл бүр ямар ч шоргоолж суллагдахгүй байж болохыг анхаарна уу.

Хамгийн сайн дарааллыг сонгохын тулд сохор номин $t$ $[l_{i}, r_{i}]$ сегмент өгөх ба тус бүрээс хэдэн шоргоолж идэж болохыг асууна.

Оролт

Эхний мөрөнд нь колоний хэмжээ болох $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоог оруулна.

Дараагийн мөрөнд $n$ ширхэг бүхэл тоо $s_{1}, s_{2}, ..., s_{n}$ ($1 ≤ s_{i} ≤ 10^{9}$) байна. Энэ нь шоргоолжны чадал юм.

Гуравдугаар мөрөнд сегментийн тоо $t$ ($1 ≤ t ≤ 10^{5}$) байна.

Дараагийн $t$ мөр бүр нь $l_{i}$, $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) байна.

Гаралт

$t$ ширхэг мөр хэвлэнэ. $i$-р мөрөнд $[l_{i}, r_{i}]$ сегментээс сохор номин идсэн шоргоолжны тоо байна.

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

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

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

Тэмдэглэл

Эхний жишээнд шоргоолж бүрийн тулааны оноо $v = [4, 0, 2, 0, 2]$ байсан ба $1$ дугаартай шоргоолж суллагдсан. Сохор номин $2$, $3$, $4$, $5$ дугаартай шоргоолжийг идсэн.

Хоёрдугаар жишээнд тулааны оноо $v = [0, 2, 0, 2]$ байсан, тэгхээр ямар ч шоргоолж суллагдаагүй бүгдийг нь

Гуравдугаар жишээнд тулааны оноо $v = [2, 0, 2]$ байсан ба $3$ ба $5$ дугаартай шоргоолж суллагдсан. Сохор номин $4$ дугаартай шоргоолжийг идсэн.

Дөрөв дүгээр жишээнд тулааны оноо $v = [0, 1]$ байсан, Тэгэхээр $5$ дугаартай шоргоолж суллагдсан. Сохор номин $4$ дугаартай шоргоолжийг идсэн.

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