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

Чамд $n$ урттай $x_{1}, x_{2}, ..., x_{n}$ бүхэл тоонуудын дараалал болон $m$ асуулгууд өгөгдсөн, асуулга бүр нь $l_{i}, r_{i}$ хоёр бүхэл тоогоор тэмдэглэгдэнэ. $f(p)$ нь $x_{k}$-нь $p$-д хуваагддаг байх $k$ индексүүдийн тоог төлөөлнө. $l_{i}, r_{i}$ асуулгын хариулт нь: нийлбэр байх ба $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-тэй тэнцүү байна.