0656 - 鉄道旅行 (Railway Trip)

JOI 鉄道は 1 本の鉄道路線を運営している．JOI 鉄道線には一直線上に並んだ N 個の駅があり，それぞれ 1 以上 N 以下の整数で番号がつけられている．各 i (1 ≤ i ≤ N - 1) に対して，駅 i と駅 i + 1 の間は線路で結ばれている．

JOI 鉄道は，K 種類の列車を走らせている．列車種別には 1 以上 K 以下の整数で番号がつけられている．また，各駅にはレベルと呼ばれる 1 以上 K 以下の整数が 1 つ定まっており，駅 i (1 ≤ i ≤ N) のレベルは L_i である．両端の駅，すなわち駅 1 および駅 N のレベルは K である．

種別 j の列車はレベルが j 以上の駅すべてに停車し，それ以外の駅には停車しない．両端の駅，すなわち駅 1 および駅 N のレベルは K なので，すべての列車が停車する．

毎日多くの利用者が JOI 鉄道線を利用する．JOI 鉄道線を利用する際には，途中で目的地と反対の方向の列車に乗ったり，目的地を通り過ぎても構わない．利用者は，駅での停車を極端に嫌うため，途中で通過する駅の数や，乗り換えの回数などによらず，できるだけ途中の停車の回数が少なくなるような経路で駅間を移動しようとする．ただし，乗り換えのための停車は，1 回の停車と数える．途中の停車の回数には，到着駅における停車は含めない．

あなたの仕事は，利用者の出発駅と到着駅が与えられたとき，この 2 駅の間を移動するための途中の停車の回数の最小値を求めるプログラムを作成することである．

課題

JOI 鉄道線の情報と，各利用者の出発駅，到着駅が与えられたとき，各利用者について，出発駅から到着駅まで移動するための途中の停車の回数の最小値を求めるプログラムを作成せよ．

入力

標準入力から以下のデータを読み込め．

• 1 行目には，整数 N, K, Q が空白を区切りとして書かれている．これは，JOI 鉄道線には N 個の駅，K 種類の列車があり，2 駅間の移動の質問が Q 個与えられることを表す．
• 続く N 行のうちの i 行目(1 ≤ i ≤ N) には，整数 L_i が書かれている．これは，駅 i のレベルが L_i であることを表す．
• 続く Q 行のうちの k 行目(1 ≤ k ≤ Q) には，整数 A_k, B_k が空白を区切りとして書かれている．これは，k 番目の利用者の出発駅，到着駅がそれぞれ駅 A_k，駅 B_k であることを表す．

出力

標準出力に Q 行で出力せよ．k 行目(1 ≤ k ≤ Q) には，駅 A_k から駅 B_k まで移動するときの，途中の停車の回数の最小値を出力せよ．

制限

すべての入力データは以下の条件を満たす．

• 2 ≤ N ≤ 100 000．
• 1 ≤ K ≤ N．
• 1 ≤ Q ≤ 100 000．
• 1 ≤ L_i ≤ K (1 ≤ i ≤ N)．
• 1 ≤ A_k ≤ N (1 ≤ k ≤ Q)．
• 1 ≤ B_k ≤ N (1 ≤ k ≤ Q)．
• A_k ≠ B_k (1 ≤ k ≤ Q)．

小課題

この課題では小課題は全部で 4 個ある．各小課題の配点および追加の制限は以下の通りである．

小課題1 [5 点]

• N ≤ 100．
• K ≤ 100．
• Q ≤ 50．

小課題2 [15 点]

• Q ≤ 50．

小課題3 [25 点]

• K ≤ 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 駅間の移動の質問が 3 個与えられる．

• 1 番目の質問は，駅 2 から駅 4 まで移動するものである．このとき，駅 2 から駅 4 まで種別 1 の列車を利用すると，途中停車する駅は駅 3 の 1 つのみとなる．
• 2 番目の質問は，駅 4 から駅 9 まで移動するものである．このとき，まず駅 4 から駅 5 まで種別 1 の列車を利用し，次に駅 5 から駅 1 まで種別 2 の列車を利用し，最後に駅 1 から駅 9 まで種別 3 の列車を利用すると，途中停車する駅は順に駅 5，駅 1，駅 8 の 3 つとなる．
• 3 番目の質問は，駅 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