JOI Railways היא חברה המפעילה מסילת רכבת אחת. במסילה של 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$. משמעותם היא שיש $N$ תחנות ב־JOI Railways, יש $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