Railway Trip

Time limit2sMemory limit512 MB

Summary

Given station levels that define which train types stop where, answer each query with the fewest intermediate stops needed to travel between two stations.

Level: Hard8 of 10
Topics: Array, Dynamic programming, Greedy
Solved: No attempts yet

Problem

JOI Railways operates one railway. The railway is a straight line of $N$ stations numbered from 1 to $N$ . For each $i$ ( $1 \le i \le N-1$ ), station $i$ and station $i+1$ are connected by a track.

JOI Railways runs $K$ types of trains, and each train runs in both directions. The train types are integers from 1 to $K$ . Each station has a level, which is an integer from 1 to $K$ . For each $i$ ( $1 \le i \le N$ ), station $i$ has level $L_i$ . Stations 1 and $N$ both have level $K$ .

A train of type $j$ ( $1 \le j \le K$ ) stops at every station whose level is at least $j$ , and at no other station. Since stations 1 and $N$ have level $K$ , every train stops at both of them.

Many passengers use the railway every day. During a trip, a passenger may take a train heading in the opposite direction from the destination, or may pass the destination. At the end, the passenger must stop at the destination. Passengers dislike stopping, so each one takes the route with the fewest intermediate stops, regardless of how many stations are passed or how many times trains are changed. If a passenger stops at a station to change trains, that counts as one stop. The first stop at the starting station and the last stop at the destination are not intermediate stops.

Write a program that answers queries on the minimum number of intermediate stops for each passenger.

Input

The first line contains three integers $N$ , $K$ , and $Q$ , the number of stations, the number of train types, and the number of queries. Each of the next $N$ lines contains one integer, the level $L_i$ of station $i$ . Each of the next $Q$ lines contains two integers $A_k$ and $B_k$ , the starting station and the destination of the $k$ -th passenger.

Output

Print $Q$ lines. The $k$ -th line contains the minimum number of intermediate stops on a route from station $A_k$ to station $B_k$ .

Constraints

$2 \le N \le 100\,000$
$1 \le K \le N$
$1 \le Q \le 100\,000$
$1 \le L_i \le K$ for $1 \le i \le N$
$1 \le A_k \le N$ for $1 \le k \le Q$
$1 \le B_k \le N$ for $1 \le k \le Q$
$A_k \neq B_k$ for $1 \le k \le Q$

Examples3

Example 1

Input

Expected output

1
3
0

Example 2
Input
```
5 2 1
2
1
1
1
2
1 4
```
Expected output
```
1
```

Example 3

Input

Expected output