Problem
a
1, a
2, ..., a
n doğal sayılarından oluşan bir dizi vardır. Alt dizilerinden bazılarını ele alalım a
l, a
l + 1, ..., a
r, burada 1 ≤ l ≤ r ≤ n ve her bir doğal sayı için s, bu alt dizide s sayısının tekrarlanma sayısını K
s ile gösterir. Bir alt dizinin önem derecesine, tüm farklı tamsayılar üzerinden K
s·K
s·s çarpımlarının toplamına s diyelim. Dizideki farklı sayıların sayısı sonlu olduğundan, toplam yalnızca sonlu sayıda sıfır olmayan terimler içerir.
Verilen t alt dizinin her birinin kardinalitesini hesaplamak gerekir.
Girdi
İlk satır iki tamsayı içerir n ve t (1 ≤ n, t ≤ 200000) — sırasıyla dizinin uzunluğu ve istek sayısı.
İkinci satır n doğal sayı içerir ai (1 ≤ a
i ≤ 10
6) — dizi öğeleri.
Sonraki t satırları iki pozitif tam sayı l ve r içerir (1 ≤ l ≤ r ≤ n) — karşılık gelen alt dizinin sol ve sağ uçlarının dizinleri.
Künye
i'nci satırın tek doğal sayıyı içerdiği t satırları yazdırın — i'inci sorgu alt dizisinin önemi.
Örnekler:
| Giriş |
Çıktı |
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 |