D. Жэфф ба үеүдийг дарах нь

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

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

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

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

Дараах $n$ элементтэй бүхэл тоон дарааллыг авч үзье: $a_1, a_2, ..., a_n$. Жэфф энэ дараалал дээр дараах үйлдлийг гүйцэтгэж чадна:

  • $a_v = a_{v+t}, a_{v+t} = a_{v+2t}, ..., a_{v+t(k-1)} = a_{v+tk}$ байх $v, t, k (1\le v,t\le n; 0\le k; v+tk\le n)$ тоонууд сонгоно.
  • $тэгээд a_v, a_{v+t}, ..., a_{v+t·k}$ элементүүдийг дарааллаас авч үлдсэн элементүүдийг шинээр $a_1,a_2,...,a_{n-k-1}$
  • $a$ дарааллын үлдсэн элементүүдийг дураар сэлгэнэ.

Дарааллын үзэмж нь дээрх үйлдлийг тухайн дараалал дээр хамгийн цөөндөө хэдэн удаа үйлдэхэд энэ дарааллын бүх элементийг нь устгах тоо юм. Жэфф $m$ ширхэг бүхэл тоо $ b_1, b_2, ..., b_m$ бичжээ. Одоо тэрээр $q$ ширхэг асуулт асуухыг хүсч байна. Асуулт бүр нь 2 ширхэг $l_i,r_i$ бүхэл тоогоох тодорхойлогдоно. Энэ асуултын хариулт нь $b_{l_i}, b_{l_i+1}, ..., b_{r_i}$ дарааллын үзэмж юм. Танд $b$ дараалал ба бүх асуултууд өгөгдөх бол хариултуудыг олж түүнд тусална уу.

Оролт

Эхний мөр $m (1\le m\le 10^5)$ бүхэл тоо агуулна. Дараагийн мөр нь $m$ ширхэг$ b_1, b_2, ..., b_m (1\le b_i\le 10^5)$ бүхэл тоонууд агуулна..

3 дахь мөрөнд асуултын тоо болох $q (1\le q\le 10^5)$ тоо өгөгдөнө.Дараагийн $q$ мөрүүд нь тус бүрдээ бүхэл тоон хос агуулна: $i$ дэх хос нь $i$ дэх асуултыг тодорхойлох $l_i, r_i (1\le l_i\le r_i \le m)$ тоонууд байна.

Гаралт

$q$ ширхэг мөрөнд асуултуудын дарааллын дагуу хариулна уу.

Орчуулсан: Төрбат

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

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