385C орчуулах · Codeforces.mn

# Баавгай ба анхны тоонууд
Саяхнаас баавгай өгөгдлийн бүтцийг судалж эхэлсэн ба дараах асуудалтай тулгарсан.

Чамд $n$ урттай $x\_{1}, x\_{2}, ..., x\_{n}$ бүхэл тоонуудын дараалал болон $m$ асуулгууд өгөгдсөн, асуулга бүр нь $l\_{i}, r\_{i}$ хоёр бүхэл тоогоор тэмдэглэгдэнэ. $f(p)$ нь $x\_{k}$-нь $p$-д хуваагддаг байх $k$ индексүүдийн тоог төлөөлнө. $l\_{i}, r\_{i}$ асуулгын хариулт нь: ![](http://espresso.codeforces.com/5e448f6c1a0e40843cecdbbeb95970464626032f.png) нийлбэр байх ба $S(l\_{i}, r\_{i})$ нь $[l\_{i}, r\_{i}]$ завсар дахь анхны тоонуудын олонлог юм (завсрын хязгааруудыг оруулна).

Баавгайн асуудлыг даван туулахад нь түүнд тусал.

## Оролт
Эхний мөр нь $n$ $(1 ≤ n ≤ 10^{6})$ бүхэл тооноос бүрдэнэ. Хоёр дахь мөр нь $n$ ширхэг $x\_{1}, x\_{2}, ..., x\_{n}$ $(2 ≤ x\_{i} ≤ 10^{7})$ бүхэл тоонуудыг агуулна. Тоонууд нь заавал ялгаатай байх шаардлагагүй.

Гурав дахь мөр нь $m$ $(1 ≤ m ≤ 50000)$ бүхэл тоог агуулна. Дараагийн $m$ мөр бүр нь зайгаар тусгаарлагдсан $l\_{i}$, $r\_{i}$ $(2 ≤ l\_{i} ≤ r\_{i} ≤ 2\*10^{9})$ бүхэл тоон хосыг агуулна. Эдгээр нь одоогийн асуулгыг тодорхойлсон тоонууд.

## Гаралт
$m$ бүхэл тоонууд хэвлэнэ. Хариултууд нь асуулгуудын оруулсан дарааллаар байна.

## Тэмдэглэл
Эхний жишээг авч үзье. Эхний жишээнд нийт гурван асуулга байна.

1. Эхний асуулганд $l = 2$, $r = 11$ байна. $f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9$ гэж тооцоолох хэрэгтэй.  
  2. Хоёр дахь асуулганд $l = 3$, $r = 12$ байна. f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7$ гэж тооцоолох хэрэгтэй. 
  3. Гурав дахь асуулганд $l = 4$, $r = 4$ байна. Энэ завсарт ямар ч анхны тоо байхгүй учраас нийбэр 0-тэй тэнцүү байна.

-- Даариймаа

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

Оролт

6
5 5 7 10 14 15
3
2 11
3 12
4 4

Гаралт

9
7
0

Оролт

7
2 3 5 7 11 4 8
2
8 10
2 123

Гаралт

0
7