B. Жижигхэн заан ба массив

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

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

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

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

Жижигхэн заан массивтай тоглох дуртай. Түүнд $1$-с $n$ хүртэл дугаарлагдсан $n$ элементтэй $a$ массив байгаа. Энд $i$ дугаартай элементийг $a_i$ гэж үзье.

Одоо жижигхэн заанд $m$ хүсэлт байгаа бөгөөд хүсэлт бүр $l_j$, $r_j$ ($1 ≤ l_j ≤ r_j ≤ n$) тоонуудаар тодорхойлогдоно. Хүсэлт бүрийн $l_j$, $r_j$-н хувьд жижигхэн заан маань $a_{l_j}, a_{l_{j+1}}, ... , a_{r_j}$ дотор яг $x$ удаа орсон $x$ тоо хэд байгааг тоолох ёстой.

Жижигхэн заанд бүх хүсэлтэнд хариулахад туслана уу.

Оролт

Эхний мөрөнд массивын хэмжээ $n$ ба хүсэлтийн тоо $m$ ($1 ≤ n, m ≤ 10^5$) өгөгдөнө. Дараагийн мөрөнд $a_1, a_2, ... , a_n$ ($1 ≤ a_i ≤ 10^9$) байх нийт $n$ ширхэг тоо байна. Дараагийн $m$ мөр хүсэлтүүдийг тодорхойлно. $j$-р мөрөнд $j$ хүсэлтийг тодорхойлох $l_j$, $r_j$ ($1 ≤ l_j ≤ r_j ≤ n$) тоонууд өгөгдөнө.

Гаралт

Хүсэлтүүдийн хариу болох нийт $m$ ширхэг мөр хэвлэнэ. $j$-р мөр нь $j$-р хүсэлтийн хариуг агуулах ёстой.

Орчуулсан: zoloogg

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

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