### PROBLEM LINK:

**Author:** Vasia Antoniuk

**Tester:** Sergey Kulik

**Editorialist:** Adury Surya Kiran

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Range Maximum Queries

### PROBLEM:

You are given an array of integers, and are asked a lot of queries (at most 10^8) like give two indices find the maximum of all the integers in the array whose index lies between those two.

### EXPLANATION:

The generation of the queries as given in the question is

x = x + 7 (mod N - 1)

y = y + 11 (mod N)

l = min(x, y)

r = max(x, y)

You need to find maximum of a* such that l <= i <= r.

The generation of (l, r) pairs is like a pseudo random procedure, so its very very hard task to find a pattern in that. Now as we got (l, r) for each query the finding maximum is quite a standard task of range queries.

There are a lot of ways to find range queries. Some of them are

- O(1) per Update and O(N) per query : Using an array, we can update each element in O(1) and when queried iterate through all elements from l to r.
- O(log N) per Update and O(log N) per query : There are a lot of ways to do this. We can use Segment trees, Binary index trees, etc.
- O(N) per Update and O(1) per query : We can use Sparse Table to solve this case.

The methods used for 2 and 3 are very standard and their explanation can be found at a lot of places.

Some useful links for solving Range Queries using Method 2 are

You can find very useful explanation of all methods including the sparse table method here in this Topcoder Tutorial.