409264: GYM103470 C Klee in Solitary Confinement

Since the traveler comes, People in Monstadt suddenly raise great interest in computer programming and algorithms, including Klee, the Spark Knight of the Knights of Favonius.

Source: Genshin Impact Official

Being sent to solitary confinement by Jean again, Klee decides to spend time learning the famous Mo's algorithm, which can compute with a time complexity of $$$\mathcal{O}(n^{1.5})$$$ for some range query problem without modifications.

To check whether Klee has truly mastered the algorithm (or in fact making another bombs secretly), Jean gives her a problem of an integer sequence $$$a_1, a_2, \cdots, a_n$$$ along with some queries $$$[l_i, r_i]$$$ requiring her to find the mode number in the contiguous subsequence $$$a_{l_i}, a_{l_i + 1}, \cdots, a_{r_i}$$$. The mode number is the most common number (that is to say, the number which appears the maximum number of times) in the subsequence.

With the help of Mo's algorithm, Klee solves that problem without effort, but another problem comes into her mind. Given an integer sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$ and an integer $$$k$$$, you can perform the following operation at most once: Choose two integers $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$ and add $$$k$$$ to every $$$a_i$$$ where $$$l \le i \le r$$$. Note that it is OK not to perform this operation. Compute the maximum occurrence of the mode number of the whole sequence if you choose to perform (or not perform) the operation optimally.

There is only one test case in each test file.

The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^6$$$, $$$-10^6 \le k \le 10^6$$$) indicating the length of the sequence and the additive number.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$) indicating the original sequence.

Output one line containing one integer indicating the maximum occurrence of the mode number of the whole sequence after performing (or not performing) the operation.

5 2
2 2 4 4 4

5

7 1
3 2 3 2 2 2 3

6

7 1
2 3 2 3 2 3 3

5

9 -100
-1 -2 1 2 -1 -2 1 -2 1

3

For the first sample test case, choose $$$l = 1$$$ and $$$r = 2$$$ and we'll result in the sequence $$$\{4, 4, 4, 4, 4\}$$$. The mode number is obviously $$$4$$$ which appears $$$5$$$ times.

For the second sample test case, choose $$$l = 4$$$ and $$$r = 6$$$ and we'll result in the sequence $$$\{3, 2, 3, 3, 3, 3, 3\}$$$. The mode number is $$$3$$$ which appears $$$6$$$ times.

For the fourth sample test case, choose not to perform the operation. The mode number is $$$1$$$ and $$$-2$$$ which both appear $$$3$$$ times.