В некотором царстве, в некотором государстве жил-был царь, и была у него дочь — Василиса Прекрасная. Многие хотели жениться на ней, но она всем отказывала. Надоело это царю, рассердился он и повелел: "Первый, кто решит мою задачку, получит Василису в жёны". Решил тогда Иванушка-дурачок счастья попытать. Пришёл к царю, а тот ему и говорит: "Вот тебе программка, введи ей N чисел, она тебе и выведет, на ком жениться. Даю тебе день на размышления". Посмотрел Иванушка на программу ту и запечалился: буквы какие-то непонятные, значки всякие, тут не только дурак, но и умный голову сломает. А между тем время кончается. Так и не придумал Иванушка ничего.

А программка та была вот такая:

C++

#include <cstdio>

const int N = ...;

int A[N];

int Q(int l, int r)
{
    if (l >= r)
        return 0;

    int m;
    int c = 0;
    int x = A[l];
    int i = l - 1;
    int j = r + 1;
    while (true)
    {
        do
        {
            --j;
            ++c;
        }
        while (A[j] > x);

        do
        {
            ++i;
            ++c;
        }
        while (A[i] < x);

        if (i < j)
        {
            int t = A[i];
            A[i] = A[j];
            A[j] = t;
        }
        else
        {
            m = j;
            break;
        }
    }

    return c + Q(l, m) + Q(m + 1, r);
}

int main()
{
    for (int i = 0; i < N; ++i)
        scanf("%d", &A[i]);

    if (Q(0, N - 1) == (N * N + 3 * N - 4) / 2)
        printf("Vasilisa the Beautiful\n");
    else
        printf("Koschei the Immortal\n");
    return 0;
}

Pascal

const
    N = ...;

var
    A: array [1..N] of integer;

function Q(l, r: integer): integer;
var
    m, c: integer;
    i, j, t, x: integer;
begin
    if l >= r then
        exit;
    
    c := 0;
    x := A[l];
    i := l - 1;
    j := r + 1;
    while true do
    begin
        repeat
            dec(j);
            inc(c)
        until A[j] <= x;
        
        repeat
            inc(i);
            inc(c)
        until A[i] >= x;
        
        if i < j then
        begin
            t := A[i];
            A[i] := A[j];
            A[j] := t
        end
        else 
        begin
            m := j;
            break
        end
    end;        
    
    Q := c + Q(l, m) + Q(m + 1, r)
end;

var
    i: integer;

begin
    for i := 1 to N do 
        read(A[i]);
    
    if Q(1, N) = (N * N + 3 * N - 4) div 2 then
        writeln('Vasilisa the Beautiful')
    else 
        writeln('Koschei the Immortal')
end.

Python

def Q(l: int, r: int) -> int:
    if l >= r:
        return 0

    c = 0
    x = A[l]
    i = l - 1
    j = r + 1
    while True:
        while True:
            j -= 1
            c += 1
            if A[j] <= x:
                break

        while True:
            i += 1
            c += 1
            if A[i] >= x:
                break

        if i < j:
            A[i], A[j] = A[j], A[i]
        else:
            m = j
            break

    return c + Q(l, m) + Q(m + 1, r)


N = ...
A = [int(x) for x in input().split()][0:N]

if Q(0, N - 1) == (N * N + 3 * N - 4) / 2:
    print('Vasilisa the Beautiful')
else:
    print('Koschei the Immortal')

Теперь, когда вы знаете программу, вы можете попытаться помочь Иванушке.

В единственной строке содержится целое число N — значение константы из программы царя (1 ≤ N ≤ 1000).

Выведите N целых чисел в пределах от −10⁹ до 10⁹, таких, что если ввести их в программу, данную царём, то она выдаст "Vasilisa the Beautiful". Числа должны быть разделены пробелами. Если возможно несколько вариантов, выведите любой.