Пусть в исходной последовательности 1 имела индекс i. Тогда что бы проверить, возможно ли это, надо для каждого j от 1 до n проверить, что . Заметим, что для каждого элемента это условие выполнится не более трёх раз, поэтому весь алгоритм будет работать за линейное время.