독방에 갇힌 클레

트래블러가 몬드에 온 뒤로 몬드 사람들은 컴퓨터 프로그래밍과 알고리즘에 큰 관심을 보이고 있다. 기사단 파보니우스의 불꽃 기사 클레도 그중 한 명이다.

출처: Genshin Impact Official

진에게 또 독방에 갇힌 클레는 시간을 보내려고 Mo's 알고리즘을 배우기로 했다. 이 알고리즘은 수정이 없는 구간 질의 문제를 $\mathcal{O}(n^{1.5})$ 시간에 계산할 수 있다.

클레가 이 알고리즘을 정말 익혔는지(아니면 몰래 폭탄을 더 만들고 있는지) 확인하려고, 진은 문제를 냈다. 정수 수열 $a_1, a_2, \cdots, a_n$과 여러 질의 $[l_i, r_i]$가 주어진다. 각 질의마다 연속 부분 수열 $a_{l_i}, a_{l_i+1}, \cdots, a_{r_i}$의 최빈값을 구해야 한다. 최빈값은 부분 수열에서 가장 많이 나타나는 수다.

Mo's 알고리즘으로 이 문제를 쉽게 푼 클레는 또 다른 문제를 떠올렸다. 길이 $n$의 정수 수열 $a_1, a_2, \cdots, a_n$과 정수 $k$가 주어진다. 다음 연산을 최대 한 번 할 수 있다. $1 \le l \le r \le n$인 두 정수 $l$, $r$을 골라 $l \le i \le r$인 모든 $a_i$에 $k$를 더한다. 연산을 하지 않아도 된다. 연산을 할지 말지를 최적으로 골라, 전체 수열의 최빈값이 나타나는 횟수의 최댓값을 구하라.

첫째 줄에 수열의 길이 $n$과 더할 수 $k$가 주어진다($1 \le n \le 10^6$, $-10^6 \le k \le 10^6$).

둘째 줄에 원래 수열 $a_1, a_2, \cdots, a_n$이 주어진다($-10^6 \le a_i \le 10^6$).

각 입력 파일에는 테스트 케이스가 하나만 들어 있다.

연산을 하거나 하지 않은 뒤, 전체 수열 최빈값의 출현 횟수 최댓값을 한 줄에 출력한다.

첫 번째 예제에서는 $l = 1$, $r = 2$를 고른다. 수열은 $\{4, 4, 4, 4, 4\}$가 된다. 최빈값은 $4$이고 $5$번 나타난다.

두 번째 예제에서는 $l = 4$, $r = 6$을 고른다. 수열은 $\{3, 2, 3, 3, 3, 3, 3\}$이 된다. 최빈값은 $3$이고 $6$번 나타난다.

네 번째 예제에서는 연산을 하지 않는다. 최빈값은 $1$과 $-2$이며, 둘 다 $3$번 나타난다.