Maximum Value

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Given an array of \(n\) non-negative integers. According to Zenyk, the beauty of a subsegment is the difference between the largest and smallest element divided by the difference of the indices of the right and left boundaries of the segment. That is, the beauty of a subsegment \([l, r]\) is equal to \(\frac{\max{(l, r)} - \min{(l, r)}}{r - l}\). Find the maximum beauty among all possible subsegments of the array with at least two elements. Also, sometimes Zenyk is interested in how many subsegments have the maximum beauty.

Input

The first line contains two integers \(n\) — the length of the array, and \(q\) — whether the number of subsegments needs to be output.

The next line contains \(n\) non-negative integers — the elements of the array.

Output

Output a single number — the maximum beauty of a subsegment, and if \(q = 1\), then output the number of subsegments with the maximum beauty separated by a space.

Constraints

\(2 \leq n \leq 10^6\),

\(0 \leq q \leq 1\),

\(0 \leq a_i \leq 10^9\).

Grading consists of the following blocks:

• 1 point for each example from the statement,

• 10 points: \(q = 0\), \(n \leq 10\), \(a_i \leq 100\),

• 14 points: \(q = 0\), \(n \leq 2000\),

• 19 points: \(q = 0\),

• 13 points: \(q = 1\), \(n \leq 10\), \(a_i \leq 100\),

• 17 points: \(q = 1\), \(n \leq 2000\),

• 25 points: without additional constraints.

You will receive the points for a block only if your program passes all tests in the block.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 0 0 5 10 6	5

Input (stdin) сopy	Output (stdout) сopy
5 1 0 7 14 10 3	7 4

Notes

In the first example, one of the solutions is the subsegment [0, 5, 10], the beauty of which is equal to 5.