Шейкерне сортування відоме в двох версіях:

• простіше, більш схоже на оптимізовану бульбашку й менш більш оптимальне передбачає, що межі left та right зсуваються назустріч одна іншій щоразу на 1;
• більш оптимальне передбачає, що межі left та right зсуваються назустріч одна іншій відповідно тому, де відбулися крайній лівий та крайній правий обміни останнього проходу.

Наразі, начебто, зроблено так, щоб цей оптимальніший варіант проходив усі тести, а менш оптимальний (де left та right зсуваються все-таки на 1) проходив усі тести, крім одного останнього.

Дано масив дійсних чисел, серед яких можуть бути як різні, так і однакові.

Відсортуйте цей масив, застосувавши шейкерне сортування (shaker sort). При перевірці значна увага буде приділена тому, як поводиться програма при майже відсортованому масиві.

Протокол взаємодії

Ваша програма повинна багатократно повторювати такі дії:

• прочитати один рядок, який містить розділені одинарними пробілами дійсні числа
  • кількість невідома, але їх точно не менше одного й не більше мільйона;
  • якщо число неціле, то ціла і дробова частини розділяються крапкою .;
• відсортувати цей масив;
• вивести його, в один рядок через одинарні пробіли
  • не намагайтеся красиво форматувати та/або заокруглювати ці числа, бо це може призвести до вердикту «неправильна відповідь»; просто виводьте через, наприклад, Console.WriteLine(string.Join(" ", arr));
• прочитати наступний рядок, яий гарантовано міститиме або єдине слово continue, або єдине слово stop (маленькими латинськими буквами, без будь-яких зайвих символів), після чого:
  • якщо це слово continue, то повторити все вказане вище для нового рядка-масиву;
  • якщо це слово stop, то завершити роботу.

Важливо виводити відсортований попередній масив до (раніше) того, як читати чергове слово continue або stop.

Приклад взаємодії

Нібито порожні рядки у прикладі зроблені суто для того, щоб краще було видно, що повинно відбутися раніше і що пізніше; вводити/виводити їх не треба.

Той самий приклад у вигляді, більш зручному для копіювання:

3 1 4
continue
3 1 4 1 5 9 2 6 3.1416
stop

Але не варто сприймати цей вигляд просто за вхідні дані, бо, повторюю, важливо виводити відсортований попередній масив до (раніше) того, як читати наступне слово continue або stop.