Problem
آرایه ای از اعداد طبیعی a
1، a
2، ...، a
n وجود دارد. برخی از زیرآرایه های آن را a
l، a
l + 1، ...، a
r، در نظر بگیرید، که در آن 1 ≤ l ≤ r ≤ n، و برای هر عدد طبیعی s با K
s تعداد دفعات اعداد s را در این زیرآرایه نشان دهید. بیایید کاردینالیته یک زیرآرایه را مجموع محصولات K
s·K
s·s روی همه اعداد صحیح متمایز s بنامیم. از آنجایی که تعداد اعداد مختلف در آرایه محدود است، مجموع آن فقط شامل تعداد متناهی جمله غیر صفر است.
لازم است که کاردینالیته های هر یک از زیرآرایه های داده شده محاسبه شود.
ورودی
خط اول شامل دو عدد صحیح n و t (1 ≤ n، t ≤ 200000) — طول آرایه و تعداد درخواست ها به ترتیب.
خط دوم شامل n عدد طبیعی ai (1 ≤ a
i ≤ 10
6) — عناصر آرایه.
خطوط t بعدی شامل دو عدد صحیح مثبت l و r (1 ≤ l ≤ r ≤ n) — شاخص های انتهای چپ و راست زیرآرایه مربوطه.
حصر
خطوط t را چاپ کنید، که در آن خط i-امین تنها عدد طبیعی — اصلی بودن زیرآرایه پرس و جو i-ام.
مثال:
<بدن>
| ورودی |
خروجی |
3 2
1 2 1
1 2
1 3
| 3
6 |
8 3
1 1 2 2 1 3 1 1 1
27
16
27 |
20
20
20 |