eolymp
bolt
Try our new interface for solving problems
Məsələlər

Экстремальная сортировка

Экстремальная сортировка

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Джон очень любит алгоритмы сортировки. Он уже изучил быструю сортировку, сортировку слиянием, поразрядную сортировку и другие.

Давным-давно он написал программу - неблокирующую сортировку строк. Это была комбинация взрывной сортировки и сортировки с мультиключом. Для реализации взрывной сортировки Вам необходимо дерево ведер. Для каждой входной строки Вы идете по дереву и кладете ее в соответствующее ведро. Когда ведро наполняется, оно "взрывается" и образует новое поддерево (с новыми ведрами).

prb7712_1.gif

Ну все, хватит о прошлом. Сегодня Джон снова занимался своим алгоритмом сортировки. На этот раз он работал с числами. У него появилась идея нового алгоритма "экстремальная сортировка". Она чрезвычайно быстрая, уровень ее производительности чуть более девяти тысяч. Перед тем как сообщить Вам ее детали, Джон хочет удостовериться в правильности ее работы.

Вам следует помочь ему убедиться в том, что так называемое экстремальное свойство имеет место после первого этапа алгоритма. Экстремальное свойство определяется как min (x[i,j]) ≥ 0, где

prb7712.gif

Giriş verilənləri

Первая строка содержит число n (1n1024). Вторая строка содержит n целых чисел a[1], a[2], ..., a[n] (1a[i]1024).

Çıxış verilənləri

Вывести "yes", если экстремальное свойство выполнено и "no" иначе.

Nümunə

Giriş verilənləri #1
2
1 2
Çıxış verilənləri #1
yes
Giriş verilənləri #2
4
2 1 3 4
Çıxış verilənləri #2
no
Mənbə 2015 German Collegiate Programming Contest (GCPC), June 20, Problem G