Codeforces Round #418 (Div. 2) problem A. An abandoned sentiment from past

小灰灰 2022-06-14 02:43 93阅读 0赞

[A. An abandoned sentiment from past][]

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

A few years ago, Hitagi encountered a giant crab, who stole the whole of her body weight. Ever since, she tried to avoid contact with others, for fear that this secret might be noticed.

To get rid of the oddity and recover her weight, a special integer sequence is needed. Hitagi's sequence has been broken for a long time, but now Kaiki provides an opportunity.

Hitagi's sequence *a* has a length of *n*. Lost elements in it are denoted by zeros. Kaiki provides another sequence *b*, whose length *k*equals the number of lost elements in *a* (i.e. the number of zeros). Hitagi is to replace each zero in *a* with an element from *b* so that **each element in *b* should be used exactly once**. Hitagi knows, however, that, **apart from 0, no integer occurs in *a* and *b* more than once in total.**

If the resulting sequence is **not** an increasing sequence, then it has the power to recover Hitagi from the oddity. You are to determine whether this is possible, or Kaiki's sequence is just another fake. In other words, you should detect whether it is possible to replace each zero in *a* with an integer from *b* so that each integer from *b* is used exactly once, and the resulting sequence is **not** increasing.

Input

The first line of input contains two space-separated positive integers *n* (2 ≤ *n* ≤ 100) and *k* (1 ≤ *k* ≤ *n*) — the lengths of sequence *a* and *b* respectively.

The second line contains *n* space-separated integers *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ 200) — Hitagi's broken sequence with exactly *k* zero elements.

The third line contains *k* space-separated integers *b*1, *b*2, ..., *b**k* (1 ≤ *b**i* ≤ 200) — the elements to fill into Hitagi's sequence.

Input guarantees that apart from 0, no integer occurs in *a* and *b* more than once in total.

Output

Output "Yes" if it's possible to replace zeros in *a* with elements in *b* and make the resulting sequence not increasing, and "No" otherwise.

Examples

input

4 2
    11 0 0 14
    5 4

output

Yes

input

6 1
    2 3 0 8 9 10
    5

output

input

4 1
    8 94 0 4
    89

output

Yes

input

7 7
    0 0 0 0 0 0 0
    1 2 3 4 5 6 7

output

Yes

Note

In the first sample:

*  Sequence *a* is 11, 0, 0, 14.
 *  Two of the elements are lost, and the candidates in *b* are 5 and 4.
 *  There are two possible resulting sequences: 11, 5, 4, 14 and 11, 4, 5, 14, both of which fulfill the requirements. Thus the answer is "Yes".

In the second sample, the only possible resulting sequence is 2, 3, 5, 8, 9, 10, which is an increasing sequence and therefore invalid.

这道题的意思就是给一个n代表第一组数据的个数，然后m代表要替换的数的个数（也是第一组数据中0的个数），然后问是否替换第一组中的0让替换后的数组成为递增序列

如果能，那么输出NO，只要有不能的情况，就输出YES；

如果只有一个0，只有这种情况才能成递增序列，所以替换后判断是不是递增序列。

如果0的个数大于一，而且题目要求每个数只能出现一次，所以替换的时候不按照递增序列替换那么整个序列就不会是递增的；

代码也比较简单明了！：

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int a[201],b[201];
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&b[j]);
        }
        if(m>1)
        {
            printf("Yes\n");
        }
        if(m==1)
        {
            for(int i=1;i<=n;i++)
            {
                if(a[i]==0)
                    a[i]=b[1];
            }
            int t=1;
            for(int i=1;i<n;i++)
            {
                if(a[i]<a[i+1])
                    continue;
                else
                {
                    t=0;
                    break;
                }
            }
            if(t==1)
                printf("No\n");
            else
                printf("Yes\n");
        }
        return 0;
    }

[A. An abandoned sentiment from past]: http://codeforces.com/contest/814/problem/A