Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

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 $H_{i}$.

Chef wants to choose a contiguous sequence of mountains $l, l+1, \ldots, 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 $(\underline{1}, \underline{5}, 2, 5, 3, \underline{7}, 2, \underline{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 $H_{1}, H_{2}, \ldots, H_{N}$.
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 \cdot last - 1) \,\%\, N + 1$.
	- Set $R$ to $(y + s \cdot 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 ≤ 10^{5}$
$0 ≤ s ≤ 1$
$1 ≤ H_{i} ≤ 10^{5}$ 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

Source: codechef | Difficulty: VERY_HARD
Tags: Data structures

Range queries

Segment trees revisited


Solutions:
from math import ceil, log

def getMid(s, e):
	return s + (e - s) // 2

def MaxUtil(st, ss, se, l, r, node):
	if l <= ss and r >= se:
		return st[node]
	if se < l or ss > r:
		return [-1, -1]
	mid = getMid(ss, se)
	a = MaxUtil(st, ss, mid, l, r, 2 * node + 1)
	b = MaxUtil(st, mid + 1, se, l, r, 2 * node + 2)
	if a[0] < b[0]:
		res = b
	else:
		res = a
	return res

def getMax(st, n, l, r):
	return MaxUtil(st, 0, n - 1, l, r, 0)

def constructSTUtil(arr, ss, se, st, si):
	if ss == se:
		st[si] = [arr[ss], ss]
		return [arr[ss], ss]
	mid = getMid(ss, se)
	a = constructSTUtil(arr, ss, mid, st, si * 2 + 1)
	b = constructSTUtil(arr, mid + 1, se, st, si * 2 + 2)
	if a[0] < b[0]:
		st[si] = b
	else:
		st[si] = a
	return st[si]

def constructST(arr, n):
	x = ceil(log(n, 2))
	max_size = 2 * pow(2, x) - 1
	st = [[-1, -1]] * max_size
	constructSTUtil(arr, 0, n - 1, st, 0)
	return st

def next(arr, n):
	s = []
	arr1 = [-1 for i in range(n)]
	for i in range(n - 1, -1, -1):
		while len(s) > 0 and arr[s[-1]] <= arr[i]:
			s.pop()
		if len(s) != 0:
			arr1[i] = s[-1]
		s.append(i)
	return arr1

def lenend(right, n):
	dic = [0] * n
	arr = [0] * n
	for i in range(n):
		arr[i] = dic[i] + 1
		if dic[right[i]] < arr[i] and right[i] != -1:
			dic[right[i]] = arr[i]
	return arr

def lenstart(right, n):
	dic = [0] * n
	arr = [0] * n
	for i in range(n - 1, -1, -1):
		if right[i] != -1:
			arr[i] = dic[right[i]] + 1
		else:
			arr[i] = 1
		if dic[i] < arr[i]:
			dic[i] = arr[i]
	return arr
(n, q, s) = map(int, input().split())
h = [int(x) for x in input().split()]
right = next(h, n)
en = lenend(right, n)
srt = lenstart(right, n)
mx = constructST(h, n)
start = constructST(srt, n)
end = constructST(en, n)
last = 0
for i in range(q):
	(x, y) = map(int, input().split())
	L = (x + s * last - 1) % n + 1
	R = (y + s * last - 1) % n + 1
	if L > R:
		(L, R) = (R, L)
	x = L - 1
	y = R - 1
	ind = getMax(mx, n, x, y)
	if ind[1] == y:
		if ind[1] == x:
			print(1)
			last = 1
		else:
			a = getMax(start, n, x, ind[1])
			last = a[0] - srt[ind[1]] + 1
			print(last)
	elif ind[1] == x:
		last = getMax(end, n, ind[1] + 1, y)[0]
		print(last)
	else:
		a = getMax(start, n, x, ind[1])
		b = getMax(end, n, ind[1] + 1, y)
		temp = a[0] - srt[ind[1]] + 1
		last = max(temp, b[0])
		print(last)