شركة JOI Railways تشغّل خط سكة حديد واحدًا. يضم هذا الخط $N$ محطة على خط مستقيم، مرقّمة من $1$ إلى $N$. لكل $i$ ($1 \le i \le N-1$)، يربط مسار سكة حديد بين المحطة $i$ والمحطة $i+1$.

لدى JOI Railways قطارات من $K$ أنواع تعمل في كلا الاتجاهين. تُمثَّل أنواع القطارات بأعداد صحيحة من $1$ إلى $K$ شاملًا. لكل محطة مستوى، وهو عدد صحيح من $1$ إلى $K$ شاملًا. لكل $i$ ($1 \le i \le N$)، مستوى المحطة $i$ هو $L_i$. مستوى المحطتين الواقعتين عند الطرفين، أي المحطة $1$ والمحطة $N$، هو $K$.

يتوقف القطار من النوع $j$ ($1 \le j \le K$) في كل محطة مستواها أكبر من أو يساوي $j$، ولا يتوقف في أي محطة أخرى. وبما أن مستوى المحطتين عند الطرفين، أي المحطة $1$ والمحطة $N$، هو $K$، فإن جميع القطارات تتوقف فيهما.

يستخدم كثير من الركاب JOI Railways يوميًا. أثناء الرحلة، يمكنهم ركوب قطار يسير في الاتجاه المعاكس للوجهة، أو تجاوز الوجهة. وفي نهاية الرحلة، يجب أن يتوقفوا في الوجهة. وهم لا يحبون التوقف في المحطات كثيرًا، لذا يحاولون اختيار مسار بأقل عدد من التوقفات الوسيطة، بغض النظر عن عدد المحطات التي يمرون بها أو عدد مرات تبديل القطارات. إذا توقف راكب في محطة لتبديل القطارات، فإننا نعدّ ذلك توقفًا واحدًا. ولا نعدّ التوقف الأول في محطة الانطلاق والتوقف الأخير في الوجهة من التوقفات الوسيطة.

مهمتك كتابة برنامج يجيب عن استعلامات حول أقل عدد من التوقفات الوسيطة لكل راكب.

المهمة

بمعرفة معلومات خط السكة الحديد التابع لشركة JOI Railways ومحطة انطلاق كل راكب ووجهته، اكتب برنامجًا يجيب عن استعلامات حول أقل عدد من التوقفات الوسيطة لكل راكب.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي.

• يحتوي السطر الأول على ثلاثة أعداد صحيحة $N,K,Q$ مفصولة بمسافات. وهذا يعني أن لدى JOI Railways عددًا قدره $N$ من المحطات و$K$ من أنواع القطارات، وأن هناك $Q$ استعلامات عن رحلات بين محطتين.
• يحتوي السطر رقم $i$ ($1 \le i \le N$) من الأسطر الـ$N$ التالية على عدد صحيح $L_i$، وهو مستوى المحطة $i$.
• يحتوي السطر رقم $k$ ($1 \le k \le Q$) من الأسطر الـ$Q$ التالية على عددين صحيحين $A_i,B_i$ مفصولين بمسافة. وهذا يعني أن محطة انطلاق الراكب رقم $k$ ووجهته هما المحطتان $A_i,B_i$ على الترتيب.

الإخراج

اطبع $Q$ أسطر في الإخراج القياسي. يحتوي السطر رقم $k$ ($1 \le k \le Q$) على أقل عدد من التوقفات الوسيطة لمسار من المحطة $A_k$ إلى المحطة $B_k$.

القيود

تستوفي جميع بيانات الإدخال الشروط التالية.

• $2 \le N \le 100\,000$.
• $1 \le K \le N$.
• $1 \le Q \le 100\,000$.
• $1 \le L_i \le K$ ($1 \le i \le N$).
• $1 \le A_k \le N$ ($1 \le k \le Q$).
• $1 \le B_k \le N$ ($1 \le k \le Q$).
• $A_k \ne B_k$ ($1 \le k \le Q$).

المهام الفرعية

هناك 4 مهام فرعية. النقاط والقيود الإضافية لكل مهمة فرعية كما يلي:

المهمة الفرعية 1 [5 نقاط]

• $N \le 100$.
• $K \le 100$.
• $Q \le 50$.

المهمة الفرعية 2 [15 نقطة]

• $Q \le 50$.

المهمة الفرعية 3 [25 نقطة]

• $K \le 20$.

المهمة الفرعية 4 [55 نقطة]

لا توجد قيود إضافية.

أمثلة

الإدخال 1

9 3 3
3
1
1
1
2
2
2
3
3
2 4
4 9
6 7

الإخراج 1

1
3
0

ملاحظة

في هذا المثال، توجد ثلاثة استعلامات عن رحلات بين محطتين.

• يتعلق الاستعلام الأول بالرحلة من المحطة $2$ إلى المحطة $4$. إذا ركب الراكب قطارًا من النوع $1$ من المحطة $2$ إلى المحطة $4$، فهناك توقف وسيط واحد فقط، في المحطة $3$.
• يتعلق الاستعلام الثاني بالرحلة من المحطة $4$ إلى المحطة $9$. إذا ركب الراكب قطارًا من النوع $1$ من المحطة $4$ إلى المحطة $5$، ثم قطارًا من النوع $2$ من المحطة $5$ إلى المحطة $1$، وأخيرًا قطارًا من النوع $3$ من المحطة $1$ إلى المحطة $9$، فهناك ثلاثة توقفات وسيطة، في المحطات $5,1,8$.
• يتعلق الاستعلام الثالث بالرحلة من المحطة $6$ إلى المحطة $7$. إذا ركب الراكب قطارًا من النوع $2$ من المحطة $6$ إلى المحطة $7$، فلا توجد توقفات وسيطة.

الإدخال 2

5 2 1
2
1
1
1
2
1 4

الإخراج 2

1

ملاحظة

لاحظ أنه يمكن للركاب تجاوز الوجهة أثناء الرحلة.

الإدخال 3

15 5 15
5
4
1
2
3
1
1
2
4
5
4
1
5
3
5
8 1
11 1
5 3
6 11
9 12
15 14
15 2
3 12
2 1
4 8
15 5
12 6
1 13
13 8
14 9

الإخراج 3

2
1
1
3
2
0
3
4
0
1
3
4
1
2
2