Пусть последовательность имеет вид a[1] a[2] ... a[N]. Возьмём член a[i]. Если a[i+1]>a[i], то и все остальные члены должны быть больше a[i]. Если меньше - соответственно, меньше. Если это верно для всех членов последовательности, то полученное дерево существует (в частности, данный путь и является таким деревом).
Поскольку у нас длина пути 50000, то квадратичный алгоритм по времени не уложится. Линейный алгоритм вышлядит так: двигаясь от конца к началу, находим максимум и минимум, попутно смотрим - если a[i+1]>a[i], то и min>a[i], а если a[i+1]<a[i], то max<a[i].
