Задан массив a, состоящий из n элементов. Каждое число от 1 до n встречается в этом массиве ровно один раз.
Для некоторых позиций i (1 ≤ i ≤ n - 1) разрешается поменять местами i-й элемент и (i + 1)-й, для остальных запрещается. Можно совершать произвольное количество операций в любом порядке. Можно менять местами i-й элемент и (i + 1)-й произовольное количество раз (если позиция разрешена).
Можно ли привести массив к отсортированному в возрастающем порядке при помощи таких операций?
В первой строке записано одно целое число n (2 ≤ n ≤ 200000) — количество чисел в массиве.
Во второй строке записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 200000) — элементы массива. Каждое число от 1 до n встречается в нем ровно один раз.
Третья строка состоит из n - 1 символа, каждый символ — либо 0, либо 1. Если i-й символ равен 1, то разрешается менять местами i-й элемент и (i + 1)-й любое количество раз, в противном случае i-й элемент и (i + 1)-й менять местами запрещено.
Если возможно отсортировать массив в возрастающем порядке с помощью любой последовательности операций, то выведите YES. В противном случае выведите NO.
6
1 2 5 3 4 6
01110
YES
6
1 2 5 3 4 6
01010
NO
В первом примере можно поменять местами a3 и a4, потом a4 и a5.
Название |
---|