Задача I. ARIMA

Входной файл:input.txt   Ограничение времени:3 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть задан временной ряд {yt}nt = 1. Требуется написать программу, вычисляющую прогноз этого ряда — значение yn + 1 с помощью модели авторегрессии ARIMA(m, k, 0).

Формат входного файла

Первая строка входных данных содержит числа n, m, k — длину ряда, глубину авторегрессии и порядок разностей временного ряда соответственно. Далее следуют n вещественных чисел — уровни ряда yt.

Формат выходного файла

Выходной файл должен содержать единственное число — прогноз n + 1 с точностью не менее четырех знаков после запятой.

Ограничения

1 < n ⩽ 105

1 ⩽ m, k ⩽ 5

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
9 2 1
2 3 4 6 9 14 22 35 56
90

0.105s 0.033s 13