Longest Uniform Subarray after Reversals

You are given a sequence (a) of length (n). A sequence is called a Shinoa sequence if all of its elements are the same. You are also given an integer (k) which represents the maximum number of operations you can perform.

For each query, you are given two integers (l) and (r). Consider the subarray (a[l..r]) (1-indexed). Initially, you can compute the length of the longest contiguous subarray (whose both endpoints lie in ([l, r])) that is a Shinoa sequence (i.e. all its numbers are identical).

However, when the operation (called "cross‐dressing") is applied on the subarray ([l, r]), the subarray transforms in the following way: choose an index (p) with (l \le p \le r), then reverse the segment (a[l..p]) and also reverse the segment (a[p+1..r]) (note that if (p = r), the second part is empty).

You may perform this operation at most (k) times (possibly zero or fewer than (k) operations) on the subarray ([l, r]). Determine the maximum possible length of a contiguous Shinoa sequence (i.e. a contiguous segment of equal numbers) that can be obtained (and which lies completely inside ([l, r])) after applying at most (k) operations.

Note: All formulas are given in (\LaTeX) format.

inputFormat

The input begins with a line containing three integers (n), (q), and (k) -- the length of the sequence, the number of queries, and the maximum number of operations allowed respectively.

The next line contains (n) integers (a_1, a_2, \dots, a_n) representing the sequence.

Each of the following (q) lines contains two integers (l) and (r) (1-indexed), indicating a query on the subarray (a[l..r]).

outputFormat

For each query, print a single line with one integer: the maximum length of a contiguous Shinoa sequence (i.e. contiguous segment in which all numbers are equal) that can be achieved in (a[l..r]) after performing at most (k) operations.

sample

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

2
2
2