Задано масив із ~n~ цілих чисел ~a_1, a_2, \ldots, a_n~ та ціле число ~k~.

Розглядаються всі відрізки масиву довжини рівно ~k~ (тобто всі підмасиви вигляду ~a_l, a_{l+1}, \ldots, a_{l+k-1}~, де ~1 \le l \le n-k+1~).

Знайдіть максимальну суму елементів серед усіх таких відрізків.

Вхідні дані

• Перший рядок містить два цілих числа ~n~ і ~k~ (~1 \le k \le n \le 2 \cdot 10^5~).
• Другий рядок містить ~n~ цілих чисел ~a_1, a_2, \ldots, a_n~ (~-10^9 \le a_i \le 10^9~).

Вихідні дані

Виведіть одне ціле число — максимальну суму серед усіх відрізків довжини ~k~.

Приклади

Приклад 1

Вхідні дані:

6 3
1 -2 3 4 -1 2

Вихідні дані:

6

Пояснення: суми всіх відрізків довжини ~3~: ~[1,-2,3] \to 2~, ~[-2,3,4] \to 5~, ~[3,4,-1] \to 6~, ~[4,-1,2] \to 5~. Максимум — ~6~.

Приклад 2

Вхідні дані:

4 4
-5 -1 -3 -2

Вихідні дані:

-11

Пояснення: при ~k=n~ існує лише один відрізок — увесь масив, тому відповідь дорівнює сумі всіх елементів.

Приклад 3

Вхідні дані:

5 1
3 -7 2 8 -1

Вихідні дані:

8

Пояснення: при ~k=1~ відповіддю є просто максимальний елемент масиву.

Задано масив із ~n~ цілих чисел ~a_1, a_2, \ldots, a_n~.

Для кожного індексу ~i~ (~1 \le i \le n~) знайдіть індекс найближчого праворуч елемента, який строго більший за ~a_i~. Якщо такого елемента не існує (тобто всі елементи праворуч від ~a_i~, включно з ним самим, не перевищують ~a_i~), виведіть для цього індексу значення ~-1~.

Формально: потрібно знайти найменший індекс ~j > i~ такий, що ~a_j > a_i~, або ~-1~, якщо такого ~j~ не існує.

Вхідні дані

• Перший рядок містить одне ціле число ~n~ (~1 \le n \le 2 \cdot 10^5~).
• Другий рядок містить ~n~ цілих чисел ~a_1, a_2, \ldots, a_n~ (~-10^9 \le a_i \le 10^9~).

Вихідні дані

Виведіть ~n~ цілих чисел через пробіл: для кожного ~i~ — індекс найближчого праворуч більшого елемента (нумерація індексів від ~1~), або ~-1~, якщо такого немає.

Приклади

Приклад 1

Вхідні дані:

5
2 1 5 3 4

Вихідні дані:

3 3 -1 5 -1

Пояснення: для ~a_1=2~ найближчий більший праворуч — ~a_3=5~ (індекс ~3~). Для ~a_2=1~ — теж ~a_3=5~ (індекс ~3~). Для ~a_3=5~ більшого елемента праворуч немає — ~-1~. Для ~a_4=3~ — ~a_5=4~ (індекс ~5~). Для ~a_5=4~ праворуч нічого немає — ~-1~.

Приклад 2

Вхідні дані:

4
4 3 2 1

Вихідні дані:

-1 -1 -1 -1

Пояснення: масив спадає, тому для кожного елемента праворуч немає більшого.

Приклад 3

Вхідні дані:

1
100

Вихідні дані:

-1

Задано ~n~ відрізків на числовій прямій. Кожен відрізок ~i~ задано парою цілих чисел ~l_i~ і ~r_i~ і складається з усіх цілих точок ~t~, для яких ~l_i \le t \le r_i~.

Знайдіть максимальну кількість відрізків, які одночасно містять якусь спільну цілу точку ~t~ (тобто максимум за всіма можливими ~t~ від кількості відрізків, що покривають цю точку).

Вхідні дані

• Перший рядок містить одне ціле число ~n~ (~1 \le n \le 2 \cdot 10^5~) — кількість відрізків.
• Далі йде ~n~ рядків, у кожному з яких — два цілих числа ~l_i~ і ~r_i~ (~1 \le l_i \le r_i \le 10^9~) — межі ~i~-го відрізка.

Вихідні дані

Виведіть одне ціле число — максимальну кількість відрізків, що покривають одну й ту саму цілу точку.

Приклади

Приклад 1

Вхідні дані:

4
1 4
2 6
3 5
10 12

Вихідні дані:

3

Пояснення: точку ~t=3~ (як і ~t=4~) покривають одразу три відрізки — перший (~[1,4]~), другий (~[2,6]~) і третій (~[3,5]~). Четвертий відрізок (~[10,12]~) з ними не перетинається.

Приклад 2

Вхідні дані:

3
1 2
3 4
5 6

Вихідні дані:

1

Пояснення: усі три відрізки не перетинаються між собою, тому в кожній точці — не більше одного відрізка.

Приклад 3

Вхідні дані:

1
7 7

Вихідні дані:

1