+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مریم آرایه $n$ عضوی $a=[a_1,a_2,...,a_n]$ را دارد. او می‌خواهد **امتیاز** $q$ تا از زیربازه‌های این آرایه را پیدا کند. **امتیاز** یک زیربازه برابر با تعداد اعدادی است که نسبت به این زیربازه **خوش‌حال** هستند. همچنین می‌دانیم عدد $k$ نسبت به زیربازه‌ی $[a_{l},a_{{l}+1},a_{{l}+2},...,a_{r}]$ **خوشحال** است اگر عدد $k$ دقیقاً $x$ بار در زیربازه آمده باشد که $cl_k \leq x \leq cr_k$ باشد.  برای مثال اگر $a$ برابر با $[1,2,1]$ باشد و $cl_1=cr_1=1$ عدد $1$ نسبت به زیربازه‌ی $1$ تا $2$ ($[1,2]$) **خوش‌حال** است چون یک بار در این بازه آمده است ولی نسبت به زیربازه‌ی $1$ تا $3$ ($[1,2,1]$) **خوش‌حال** نیست چون دو بار در این بازه آمده است و $cr_1 < 2$. # ورودی در سطر اول ورودی، سه طبیعی $n$ که طول آرایه، $m$ که حداکثر عدد آرایه و $q$ که تعداد زیربازه‌هایی است که مریم می‌خواهد امتیاز آن‌ها را بداند. $$1\leq n, m, q \leq 300\,000$$ در سطر بعدی $n$ عدد $a_1, a_2, \dots, a_n\,$ آمده که اعضای آرایه را نشان می‌دهند. $$1 \leq a_i \leq m$$ در $m$ سطر بعدی، در سطر $i$ام بعدی دو عدد $cl_i$ و $cr_i$ آمده است. $$1\leq cl_i \leq cr_i \leq 300\,000$$ در هر کدام از $q$ سطر بعدی دو عدد آمده است که بازه‌ای را که مریم می‌خواهد امتیاز آن را پیدا کند. پس در سطر $i$ام از این $q$ سطر بعدی دو عدد $l_i, r_i$ آمده است که مریم امتیاز $[a_{l_i},a_{{l_i}+1},a_{{l_i}+2},...,a_{r_i}]\quad$ را می‌خواهد پیدا کند. # خروجی در تنها سطر خروجی $q$ عدد چاپ کنید که عدد $i$ام امتیاز زیربازه‌ی $[a_{l_i},a_{{l_i}+1},a_{{l_i}+2},...,a_{r_i}]\quad$ است. # مثال‌ها ## ورودی نمونه ۱ ``` 6 3 4 1 2 3 1 2 1 2 3 1 1 1 1 1 6 1 4 3 5 4 4 ```` ## خروجی نمونه ۱ ``` 2 3 2 0 ```` در این مثال آرایه $a$ به صورت $[1, 2, 3, 1, 2, 1]$ است. عدد `1` زمانی خوشحال است که بین $[2, 3]$ بار تکرار شود. عدد `2` و `3` زمانی خوشحال هستند که دقیقاً $1$ بار ظاهر شوند. + زیر بازه‌ی اول از ۱ تا ۶ (یعنی $[1, 2, 3, 1, 2, 1]$) است. که اعداد ۱ و ۳ خوشحال هستند پس امتیاز آن ۲ است. + زیر بازه‌ی دوم از ۱ تا ۴ (یعنی $[3, 1, 2, 1]$) است. که اعداد ۱، ۲ و ۳ خوشحال هستند پس امتیاز آن ۳ است. + زیر بازه‌ی سوم از ۳ تا ۵ (یعنی $[3, 1, 2]$) است. که اعداد ۲ و ۳ خوشحال هستند پس امتیاز آن ۲ است. + زیر بازه‌ی چهارم از ۴ تا ۴ (یعنی $[1]$) است. که هیچ عددی خوشحال نیست، پس امتیاز آن ۰ است.

حل سؤال در بانک سؤالات