Проверка, можно ли упорядочить массив с помощью стека
Дан массив чисел
1, 2, 3, ..., n, расположенных в произвольном порядке. Необходимо определить, является ли этот массив стек-сортируемым. Массив A называется стек-сортируемым, если существует способ с помощью дополнительного стека получить массив B, который в конце выполнения алгоритма будет упорядочен по возрастанию. Разрешенные операции следующие:- Забрать первый элемент из
Aи поместить его на вершину стека.
- Снять элемент с вершины стека и добавить его в конец
B.
Если после этих операций массив
B оказывается отсортирован по возрастанию, значит A является стек-сортируемым.Входные данные
В первой строке входных данных дано целое число
n (1 ≤ n ≤ ).Во второй строке содержатся
n целых чисел (1 ≤ ≤ n).Выходные данные
Программа должна вывести
Yes, если A можно стек-отсортировать, и No в противном случае.Примеры
Input | Input |
4
4 1 2 3 | Yes |
3
3 2 1 | Yes |
3
1 2 3 | Yes |
4
2 4 1 3 | No |
Пояснение
A = [4, 1, 2, 3], S = [], B = []
- Operation 1:
A = [1, 2, 3],S = [4],B = []
- Operation 1:
A = [2, 3],S = [4, 1],B = []
- Operation 2:
A = [2, 3],S = [4],B = [1]
- Operation 1:
A = [3],S = [4, 2],B = [1]
- Operation 2:
A = [3],S = [4],B = [1, 2]
- Operation 1:
A = [],S = [4, 3],B = [1, 2]
- Operation 2:
A = [],S = [4],B = [1, 2, 3]
- Operation 2:
A = [],S = [],B = [1, 2, 3, 4]
A = [3, 2, 1], S = [], B = []
- Operation 1:
A = [2, 1],S = [3],B = []
- Operation 1:
A = [1],S = [3, 2],B = []
- Operation 1:
A = [],S = [3, 2, 1],B = []
- Operation 2:
A = [],S = [3, 2],B = [1]
- Operation 2:
A = [],S = [3],B = [1, 2]
- Operation 2:
A = [],S = [],B = [1, 2, 3]
A = [1, 2, 3], S = [], B = []
- Operation 1:
A = [2, 3],S = [1],B = []
- Operation 2:
A = [2, 3],S = [],B = [1]
- Operation 1:
A = [3],S = [2],B = [1]
- Operation 2:
A = [3],S = [],B = [1, 2]
- Operation 1:
A = [],S = [3],B = [1, 2]
- Operation 2:
A = [],S = [],B = [1, 2, 3]
Невозможно стек-отсортировать массив [2, 4, 1, 3]
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 10 MB