Codeforce 920C Swap Adjacent Elements

Posted on | In | 阅读

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 a1, a2, …, 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.

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

1
2
3
6
1 2 5 3 4 6
01110

output

1
YES

input

1
2
3
6
1 2 5 3 4 6
01010

output

1
NO

Note

In the first example you may swap a3 and a4, and then swap a4 and a5.

  • 每段连续的1以及最后一个1右边的位置的数都是可以相互交换的，但是和其他的部分之间不能互换，所以每段区间[l, r]不能出现超出区间[l+1, r+1]范围的数
  • 剩余的部分就是不能进行交换的部分，即数必须等于下标+1

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define N 200001

using namespace std;

int arr[N];
char str[N];


int main()
{
    int num;
    bool flag = true;
    while(~scanf("%d", &num))
    {
        flag = true;
        for(int i = 0; i < num; i++)
        {
            scanf("%d", &arr[i]);
        }
        scanf("%s", str);
        getchar();
        for(int i = 0; i < num; i++)
        {
            int l = i;
            while(str[i] == '1' && i < num-1)
                i++;
            int r = i;
            if(l == r && arr[l] != l+1)
            {
//                cout << "sdf: " << l << endl;
                flag = false;
                break;
            }
            for(int j = l; j <= r; j++)
            {
                if(arr[j] > r+1 || arr[j] < l+1)
                {
//                    cout << l << ' ' << r << endl;
                    flag = false;
                    break;
                }
            }
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}