JOI Railways — бір теміржол желісін басқаратын компания. JOI Railways теміржолында бір түзудің бойында $1$-ден $N$-ге дейін нөмірленген $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$ сұраныс берілгенін білдіреді.
• Келесі $N$ жолдың $i$-ші жолында ($1\le i\le N$) $i$ станциясының деңгейін білдіретін бір бүтін сан $L_i$ берілген.
• Келесі $Q$ жолдың $k$-шы жолында ($1\le k\le 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$ станциясына сапар туралы. Егер жолаушы $2$ станциясынан $4$ станциясына дейін $1$ түріндегі пойызға мінсе, онда тек бір ғана аралық аялдама — $3$ станциясы болады.
• Екінші сұраныс $4$ станциясынан $9$ станциясына сапар туралы. Егер жолаушы $4$ станциясынан $5$ станциясына дейін $1$ түріндегі пойызға, содан кейін $5$ станциясынан $1$ станциясына дейін $2$ түріндегі пойызға, ал соңында $1$ станциясынан $9$ станциясына дейін $3$ түріндегі пойызға мінсе, онда үш аралық аялдама — $5,1,8$ станциялары болады.
• Үшінші сұраныс $6$ станциясынан $7$ станциясына сапар туралы. Егер жолаушы $6$ станциясынан $7$ станциясына дейін $2$ түріндегі пойызға мінсе, аралық аялдамалар болмайды.

Кіріс деректер 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