Page Contents

## Unusual Queries November Challenge 2020

There are N mountains in Chefland, arranged in a line and numbered 1 through N from left to right. For each valid i, the i-th mountain from the left has a height Hi.

Chef wants to choose a contiguous sequence of mountains l,l+1,…,r and visit them in this order. He has a notebook where he writes down some heights of mountains. Initially, the notebook contains only the integer 0 and each time he visits a new mountain whose height is strictly greater than all the integers written in the notebook so far, he writes its height in the notebook. The satisfaction Chef gets from travelling is the number of positive integers written in the notebook at the end. For example, if the mountains have heights (1–,5–,2,5,3,7–,2,9–), Chef’s satisfaction is 4 and the integers written in the notebook at the end are 0,1,5,7,9.

Your task is to answer Q queries. In each query, Chef gives you two integers L and R (1≤L≤R≤N) and you should find the maximum satisfaction he can get if he can choose to visit any contiguous sequence of mountains from l to r such that L≤l≤r≤R. Note that the queries are encoded in such a way that they have to be processed online.

Input

The first line of each test case contains three space-separated integers N, Q and s.

The second line contains N space-separated integers H1,H2,…,HN.

Each of the following Q lines contains two space-separated integers x and y describing a query. The parameters L and R for this query can be computed as follows:

Let last be the answer to the previous query, or 0 if this is the first query in this test case.

Set L to (x+s⋅last−1)%N+1.

Set R to (y+s⋅last−1)%N+1.

If L>R, swap L and R.

Output

For each query, print a single line containing one integer — the maximum satisfaction Chef can get.

Constraints

1≤N,Q≤105

0≤s≤1

1≤Hi≤105 for each valid i

1≤x,y≤N

Subtasks

Subtask #1 (15 points): N≤1,000

Subtask #2 (35 points): s=0, i.e. the queries do not have to be processed online

Subtask #2 (50 points): original constraints

Example Input 1

6 3 0

4 2 3 1 5 5

1 6

2 4

3 4

Example Output 1

3

2

1

Explanation

In the first query, Chef can choose to visit a contiguous subsequence of mountains with heights (4,2,3,1,5,5). The subsequence that gives the maximum satisfaction is (2,3,1,5). In that case, Chef writes the integers 0,2,3,5 to his notebook, so the answer is 3.

In the second query, Chef can choose to visit a contiguous subsequence of mountains with heights (2,3,1). The whole sequence has the maximum satisfaction 2, since Chef writes the integers 0,2,3.

In the third query, the largest (and the only possible) satisfaction is 1, since Chef writes either 0,3 or 0,1.

Example Input 2

10 10 1

7 8 8 9 10 10 2 3 5 10

9 6

2 9

10 6

4 2

5 10

4 5

8 7

8 2

7 7

9 5

Example Output 2

3

3

3

1

4

2

2

4

1

4

*Solution:*nqs = list(map(int , input().split()))

n = nqs[0]

q = nqs[1]

s = nqs[2]

a = list(map(int , input().split()))

b = arr = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(1,n+1):

ctr = 1

curr = a[i-1]

b[i][i] = 1

for j in range(i+1 , n+1):

if(a[j-1] > curr):

ctr += 1

curr = a[j-1]

b[i][j] = ctr

for i in range(1,n+1):

best = 1

for j in range(n,0,-1):

best = max(best , b[j][i])

b[j][i] = best

for i in range(1,n+1):

best =b[i][i]

for j in range(i+1 , n+1):

best = max(best , b[i][j])

b[i][j] = best

last = 0

for _ in range(q):

lr = list(map(int, input().split()))

l = lr[0]

r = lr[1]

l = (l + s*last -1)%n +1

r = (r + s*last -1)%n +1

if(l > r):

l = l^r

r = l^r

l = l^r

last = b[l][r]

print(last)

**Chegg FREE****Premium****Accounts:**

*Udemy Leak Courses:*### November Challenge 2020 SOLUTION CodeChef

- Selecting Edges SOLUTION SELEDGE
- Panic! at the Disco SOLUTION PANIC
- Restore Sequence SOLUTION RESTORE

### October Lunchtime 2020 CodeChef SOLUTIONS

*RELATED :*