Максимальне Значення

Обмеження: 2 сек., 512 МіБ

Дано масив з \(n\) цілих невід’ємних чисел. На думку Зеника, краса підвідрізка — це різниця найбільшого і найменшого елемента поділена на різницю індексів правої і лівої межі відрізка. Тобто краса підрвізка \([l, r]\) рівна \(\frac{\max{(l, r)} - \min{(l, r)}}{r - l}\). Знайдіть максимальну красу серед всіх можливих підвідрізків масиву з принаймі двох елементів. Також іноді Зеника цікавить скільки є підвідрізків з максимальною красою.

Вхідні дані

У першому рядку задано два цілі числа \(n\) — довжина масиву і \(q\) — чи потрібно виводити кількість підвідрізків.

В наступному рядку задано \(n\) цілих невід’ємних чисел — елементи масиву.

Вихідні дані

Виведіть одне число — максимальну красу підвідрізка, і якщо q = 1, то через пробіл виведіть кількість підвідрізків з максимальною красою.

Обмеження

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

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

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

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 10 балів: \(q = 0\), \(n \leq 10\), \(a_i \leq 100\),

• 14 балів: \(q = 0\), \(n \leq 2000\),

• 19 балів: \(q = 0\),

• 13 балів: \(q = 1\), \(n \leq 10\), \(a_i \leq 100\),

• 17 балів: \(q = 1\), \(n \leq 2000\),

• 25 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 0 0 5 10 6	5

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 1 0 7 14 10 3	7 4

Примітки

У першому прикладі, одним із розв’язків є підвідрізок [0, 5, 10], краса якого дорівнює 5.