Late Knight's Optimal Victory Strategy

In the year 1491, Duke Milan Lodovico Sforza organized a grand three‐day jousting tournament for his wedding celebration. However, the most popular knight was late. In the tournament, N knights are involved. Initially, N-1 knights are arranged in a row and are assigned indices from 0 to N-2. In each round of the contest, the host announces two indices S and E (with 0 ≤ S < E ≤ current_lineup_length-1). All knights between positions S and E (inclusive) compete against each other. The knight with the highest strength in the chosen segment wins the round and remains in his position, while all the other competing knights are eliminated from the tournament. Afterwards, the remaining knights shift forward to close the gaps, and the positions are updated from 0 onwards. This process continues for C rounds until only one knight remains.

Leonardo, the mastermind behind the celebrations, knows that all knights have distinct strength values ranging from 0 (weakest) to N-1 (strongest), and that in every round the knight with the maximum strength among the competitors wins. However, one knight – the late knight with strength R – has not yet arrived. Leonardo wants to determine the best position to insert this late knight into the initial arrangement (of N-1 knights) so that in the rounds which include him, he wins as many rounds as possible. Only rounds in which the late knight competes and wins are counted.

For example, consider a tournament with 5 knights where the pre-arranged knights have strengths [1, 0, 2, 4] and the late knight has strength 3. Suppose there are 3 rounds and the host calls out positions (S, E) as follows:

Round 1: (1, 3) Round 2: (0, 1) Round 3: (0, 1)

If Leonardo inserts the late knight at position 0, the lineup becomes [3, 1, 0, 2, 4]. In Round 1, knights at positions 1 to 3 (with strengths [1, 0, 2]) compete, and the knight with strength 2 wins. After the elimination and compression the lineup becomes [3, 2, 4]. In Round 2, positions 0 and 1 (with strengths [3, 2]) compete and the knight with strength 3 (the late knight) wins. Finally, in Round 3, the remaining knights [3, 4] compete and the knight with strength 4 wins. Here, the late knight only wins 1 round.

Conversely, if Leonardo inserts the late knight between the knights with strengths 1 and 0, the lineup becomes [1, 3, 0, 2, 4]. Now, in Round 1, the participants are [3, 0, 2] (positions 1 to 3) and the late knight wins because his strength (3) is the highest among them. After the round, the lineup becomes [1, 3, 4]. In Round 2, the competitors are [1, 3] and the late knight wins again. In Round 3, the lineup [3, 4] produces a win for the knight with strength 4. In this case, the late knight wins 2 rounds, which is optimal.

Your task is to write a program that, given the initial arrangement of the pre-arranged knights, the late knight's strength, and the list of rounds (each with positions S and E), determines the maximum number of rounds in which the late knight can participate and win by choosing an optimal insertion position.

inputFormat

The first line contains three integers: N, C, and R, where N is the total number of knights (including the late knight), C is the number of rounds, and R is the strength of the late knight. The second line contains N-1 integers, representing the strengths of the pre-arranged knights in order. Each of the next C lines contains two integers S and E (with 0 ≤ S < E ≤ current_lineup_length-1) that denote the positions for that round's competition.

outputFormat

Output a single integer: the maximum number of rounds in which the late knight can participate and win if he is inserted optimally.

sample

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

2