Minimizing Exam Stress

At T University, Xiao Fun Rabbit faces a series of final exams this semester, numbered from \(1\) to \(n\) with respective difficulty coefficients \(a_1, a_2, \ldots, a_n\). To mitigate stress, he can choose to prepare for only the first \(k\) exams (where \(0 \le k \le n\)), postponing the remaining exams. However, postponed exams will need to be taken in the next semester.

The stress value \(t\) is computed as follows:

[ t = \max_{1 \le i \le k} a_i + c \times (n - k), ]

with the convention that \(\max_{1 \le i \le 0} a_i = 0\) when \(k = 0\).

Your task is to determine the optimal number of exams \(k\) (i.e. exams to prepare) that minimizes the stress value \(t\). If there are multiple values of \(k\) that produce the minimum stress, output the corresponding \(k\).

inputFormat

The input consists of two lines:

• The first line contains two integers \(n\) and \(c\) \((1 \le n \le 10^5,\ 1 \le c \le 10^9)\), the number of exams and the stress coefficient respectively.
• The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\), representing the difficulty coefficients of each exam in order.

outputFormat

Output a single integer: the optimal number \(k\) (\(0 \le k \le n\)) of exams to prepare such that the stress value \(t\) is minimized.

sample

5 2
3 1 4 1 5

5