Problem Description

Given \( n, k \) and a sequence of length \( n \), you can choose to add \( k \) to all elements in a subinterval \([l, r]\) or do nothing. Determine the maximum frequency of the mode number after performing this operation optimally.

Problem Description

Since the traveler's arrival, the people of Monstadt, including Klee, the Spark Knight of the Knights of Favonius, have developed a keen interest in computer programming and algorithms.

Sent to solitary confinement by Jean again, Klee decides to spend her time learning the famous Mo's algorithm, which can solve certain range query problems without modifications in \(\mathcal{O}(n^{1.5})\) time complexity.

To verify if Klee has truly mastered the algorithm (or if she is secretly making more bombs), Jean presents her with a problem involving an integer sequence \( a_1, a_2, \ldots, a_n \) and queries \([l_i, r_i]\), asking her to find the mode number in the sub-sequence \( a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i} \). The mode number is the most frequent number in the sub-sequence.

With the help of Mo's algorithm, Klee easily solves this problem, but another thought strikes her. Given an integer sequence \( a_1, a_2, \ldots, 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 \). It is also acceptable not to perform this operation. Compute the maximum frequency of the mode number of the entire sequence after performing (or not performing) the operation optimally.

Input Format

There is only one test case per test file.

The first line of 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 input contains \( n \) integers \( a_1, a_2, \ldots, a_n \) (\( -10^6 \le a_i \le 10^6 \)) indicating the original sequence.

Output Format

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

Sample Input and Output

Sample Input #1

5 2
2 2 4 4 4

Sample Output #1

5

Sample Input #2

7 1
3 2 3 2 2 2 3

Sample Output #2

6

Sample Input #3

7 1
2 3 2 3 2 3 3

Sample Output #3

5

Sample Input #4

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

Sample Output #4

3

Notes

For the first sample test case, choosing \( l = 1 \) and \( r = 2 \) results in the sequence \(\{4, 4, 4, 4, 4\}\). The mode number is \( 4 \), appearing \( 5 \) times.

For the second sample test case, choosing \( l = 4 \) and \( r = 6 \) results in the sequence \(\{3, 2, 3, 3, 3, 3, 3\}\). The mode number is \( 3 \), appearing \( 6 \) times.

For the fourth sample test case, not performing the operation results in the mode numbers \( 1 \) and \( -2 \), both appearing \( 3 \) times.

见题面 Input 部分

见题面 Output 部分