Swap Adjacent Elements

题意翻译

输入格式: 第一行一个整数 n (2≤n≤200000) 第二行 n个整数 a1,a2,⋯,an(1≤ai​≤200000) 。每个 1 到 n 间的整数正好出现一次。 第三行一个字符串,只包含 0 或者 1 。如果第 i个字符是1 ,你就可以把 ai与 ai+1交换。 输出格式: 如果可以排序,输出 YES,否则输出 NO。 感谢@小粉兔 提供的翻译

题目描述

You have an array $ a $ consisting of $ n $ integers. Each integer from $ 1 $ to $ n $ appears exactly once in this array. For some indices $ i $ ( $ 1<=i<=n-1 $ ) it is possible to swap $ i $ -th element with $ (i+1) $ -th, for other indices it is not possible. You may perform any number of swapping operations any order. There is no limit on the number of times you swap $ i $ -th element with $ (i+1) $ -th (if the position is not forbidden). Can you make this array sorted in ascending order performing some sequence of swapping operations?

输入输出格式

输入格式


The first line contains one integer $ n $ ( $ 2<=n<=200000 $ ) — the number of elements in the array. The second line contains $ n $ integers $ a_{1} $ , $ a_{2} $ , ..., $ a_{n} $ ( $ 1<=a_{i}<=200000 $ ) — the elements of the array. Each integer from $ 1 $ to $ n $ appears exactly once. The third line contains a string of $ n-1 $ characters, each character is either 0 or 1. If $ i $ -th character is 1, then you can swap $ i $ -th element with $ (i+1) $ -th any number of times, otherwise it is forbidden to swap $ i $ -th element with $ (i+1) $ -th.

输出格式


If it is possible to sort the array in ascending order using any sequence of swaps you are allowed to make, print YES. Otherwise, print NO.

输入输出样例

输入样例 #1

6
1 2 5 3 4 6
01110

输出样例 #1

YES

输入样例 #2

6
1 2 5 3 4 6
01010

输出样例 #2

NO

说明

In the first example you may swap $ a_{3} $ and $ a_{4} $ , and then swap $ a_{4} $ and $ a_{5} $ .