Problem
Terdapat tatasusunan nombor asli a
1, a
2, ..., a
n. Pertimbangkan beberapa subarraynya a
l, a
l + 1, ..., a
r, dengan 1 ≤ l ≤ r ≤ n, dan bagi setiap nombor asli s menandakan dengan K
s bilangan kejadian nombor s dalam subbaris ini. Mari kita panggil kardinaliti subarray sebagai jumlah produk K
s·K
s·s atas semua integer yang berbeza s. Oleh kerana bilangan nombor berbeza dalam tatasusunan adalah terhingga, jumlahnya hanya mengandungi bilangan terhingga sebutan bukan sifar.
Ia adalah perlu untuk mengira kardinaliti setiap t subarray yang diberikan.
Input
Baris pertama mengandungi dua integer n dan t (1 ≤ n, t ≤ 200000) — panjang tatasusunan dan bilangan permintaan, masing-masing.
Baris kedua mengandungi n nombor asli ai (1 ≤ a
i ≤ 10
6) — elemen tatasusunan.
Garis t seterusnya mengandungi dua integer positif l dan r (1 ≤ l ≤ r ≤ n) — indeks hujung kiri dan kanan subarray yang sepadan.
Cetakan
Cetak garisan t, di mana baris ke-i mengandungi satu-satunya nombor asli — kardinaliti subbaris pertanyaan ke-i.
Contoh:
| Input |
Output |
3 2
1 2 1
1 2
1 3
| 3
6 |
8 3
1 1 2 2 1 3 1 1
27
16
27 |
20
20
20 |