CodeForces-920C Swap Adjacent Elements

链接：https://codeforces.com/problemset/problem/920/C

$Time\;Limit:\;1000\;ms$

$Memory\;Limit:\;262144\;kB$

Description

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?

Input

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$ - 1characters, 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.

Output

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.

Examples

Input

6
1 2 5 3 4 6
01110

Output

YES

Input

6
1 2 5 3 4 6
01010

Output

NO

Note

In the first example you may swap $a$3 and $a$4, and then swap $a$4 and $a$5.

题解

水题，找出不在自己位置的点，判断其到自己正确位置的路径上是否全部可以交换即可

这里统计路径上1的个数作为判断标准

//Time: 311ms Memory: 2068kB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5 + 5;
int a[N], sum[N];
int main()
{
	int n; string str;
	cin >> n;
	a[0] = 0;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	cin >> str;
	sum[0] = str[0];
	for(int i = 1; i <= n; ++i) sum[i] = str[i - 1] - '0' + sum[i - 1];
	for(int i = 1; i <= n; ++i)
	{
		if(a[i] == i) continue;
		if(a[i] < i)
		{
			if(sum[i - 1] - sum[a[i] - 1] != i - a[i])
			{
				cout << "NO" << endl;
				return 0;
			}
		}
		else
		{
			if(sum[a[i] - 1] - sum[i - 1] != a[i] - i)
			{
				cout << "NO" << endl;
				return 0;
			}
		}
	}
	cout << "YES" << endl;
}