e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dynamic Programming - Linear

Метеоспостереження

prb3869 Олексій вчиться у п'ятому класі і збирається стати метеорологом. Нещодавно Олексій завів щоденник, у який заніс щоденні вимірювання температури у рідному місті. Олексій знайшов архівні дані за останні декілька сотень років, а це означає, что даних у нього дуже і дуже багато. Програмувати Олексій не вміє і просить Вас написати програму, яка обчислює середню температуру за k послідовних днів, причому такі значення йому потрібні за весь період спостережень:

  • Середня температура з 1 по k-ий день
  • Середня температура з 2 по (k + 1)-ий день
  • І так далі, доки є дані.

А після цього з усіх обчислених значень Олексію потрібні лише два числа - мінімальні та максимальні значення. Допоможіть Олексію і напишіть для нього цю програму.

Вхідні дані

У першому рядку містяться два цілих числа n та k - кількість вимірювань температури та кількість днів для обчислення середньої температури (1kn105). У наступному рядку міститься n цілих чисел - дані вимірювань температури. Кожне з цих чисел знаходиться в інтервалі (-100, 100).

Вихідні дані

Вивести два рядки, які містять мінімальну і максимальну середню температуру, знайдену на відрізках довжини k. Число округліть до найближчого цілого.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 2
10 12 18 14
Вихідні дані #1
11
16
Джерело Задачи отборочного тура Всероссийской командной олимпиады школьников 2011/2012 учебный год