• Иванушка
  GABY IVANUSHKA

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

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

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

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

На языке Pascal:
 
var A:array [1..N] of longint;
     c:longint;
     i:integer;
function P(l,r:longint):longint;
var i,j,t,x:longint;
begin
    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 
                            P:=j; 
                            exit
                     end
    end
end;
procedure Q(l,r:longint);
var n:longint;
begin
         if l<r then
                      begin
                            n:=P(l,r);
                            Q(l,n);
                            Q(n+1,r)
                      end
end;
begin
       c:=0;
       for i:=1 to N do 
            read(A[i]);
       Q(1,N);
        if c=(N*N+3*N-4) div 2 
             then
                  writeln ('Василиса Прекрасная')
             else
                  writeln ('Кощей Бессмертный')
end.

На языке C:
 
 #include <stdio.h>  
 long c;
 long A[N]; 
 long P(long l, long r)
 {
  long x=A[l],
       i=l-1,
       j=r+1,
       t;
  while(1)
 {
  do{--j; ++c;}
  while(A[j]>x);
  do{++i; ++c;}
  while(A[i]<x);
  if(i<j)
    {
      t=A[i];
      A[i]=A[j];
      A[j]=t;
    }
  else return j;
 }
}
 
 void Q(long l, long r)
 {
  long n;
  if(l<r)
    {
     n=P(l,r);
     Q(l,n);
     Q(n+1,r);
    }
 }
 
 int main(void)
 {
   c=0;
   for(long i=0; i<N; ++i)
   scanf("%ld", &A[i]);
   Q(0,N-1);
   if(c==(N*N+3*N-4)/2)
        printf ("Василиса Прекрасная");
  else 
        printf ("Кощей Бессмертный");
  return 0;
 }

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

Технические требования:  

Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: до 5 секунд на один тест

Входной файл: в первой строке содержится число натуральное число N<=1000.

Выходной файл: вы должны вывести N чисел в одной строке таких, что если ввести их в программу, данную царём, то она выдаст "Василиса Прекрасная". Числа должны быть разделены пробелами. Если возможно несколько вариантов, выведите любой.

Пример:

INPUT.TXT

3

OUTPUT.TXT

3 7 19