351D орчуулах · Codeforces.mn

# Жэфф ба үеүдийг дарах нь
Дараах $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$ ширхэг мөрөнд асуултуудын дарааллын дагуу хариулна уу.

-- Төрбат

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

Оролт

Гаралт

Оролт

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

Гаралт