• محدودیت زمان: ۱.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

مریم آرایه $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]$) است. که هیچ عددی خوشحال نیست، پس امتیاز آن ۰ است.