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

---

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