Задача . B. Неправильный ответ

Рассмотрим следующую задачу: дан массив \(a\), содержащий \(n\) целых чисел (пронумерованных от \(0\) до \(n-1\)), найдите \(\max\limits_{0 \leq l \leq r \leq n-1} \sum\limits_{l \leq i \leq r} (r-l+1) \cdot a_i\). В этой задаче \(1 \leq n \leq 2\,000\) и \(|a_i| \leq 10^6\).

Попытавшись решить эту задачу, Алиса сразу придумала сногсшибательно-быстрый алгоритм и запрограммировала его. Псевдокод ее реализации такой:

function find_answer(n, a)
    # Assumes n is an integer between 1 and 2000, inclusive
    # Assumes a is a list containing n integers: a[0], a[1], ..., a[n-1]
    res = 0
    cur = 0
    k = -1
    for i = 0 to i = n-1
        cur = cur + a[i]
        if cur < 0
            cur = 0
            k = i
        res = max(res, (i-k)*cur)
    return res

Как вы можете видеть, идея Алисы не отличается правильностью. Например, положим \(n = 4\) и \(a = [6, -8, 7, -42]\). Тогда find_answer(n, a) вернет \(7\), но правильный ответ \(3 \cdot (6-8+7) = 15\).

Вы сказали Алисе, что ее решение неправильное, но она вам не поверила.

Дано целое число \(k\), ваша задача — найти любую последовательность \(a\) из \(n\) целых чисел такую, что правильный ответ для нее и ответ алгоритма Алисы отличается ровно на \(k\). Обратите внимание, что не смотря на то, что вы сами выбираете \(n\) и содержание последовательности, вы все равно должны следовать данным ограничениям: \(1 \leq n \leq 2\,000\) и абсолютная величина каждого элемента последовательности не должна превосходить \(10^6\). Если такой последовательности нет, вы должны это определить.