Дана последовательность a[n]
целых чисел, состоящая из n элементов. Для заданного числа k найдите непустую подпоследовательность a[i]
, a[i+1]
, ... a[i+m]
подряд идущих элементов последовательности a[n]
, такую, что сумма ее элементов максимально близка к k.
В первой строке содержатся два целых числа n и k (1 ≤ n ≤ 500000, -10^9
≤ k ≤ 10^9
) – количество элементов в последовательности и желаемая сумма. Во второй строке следуют n целых чисел a[i]
(-10^9
≤ a[i]
≤ 10^9
) - элементы последовательности.
Вывести одно число |k - l| (модуль разности k – l), где l – сумма чисел оптимального сегмента последовательности.