Борис думает, что шахматы это скучная игра, поэтому он ушел со своего турнира пораньше. Он пошел в парикмахерскую, ведь его прическа была немного неаккуратная.
В настоящий момент его волосы можно описать массивом \(a_1,a_2,\ldots, a_n\), где \(a_i\) — высота волоса на позиции \(i\). Его желаемая прическа описывается массивом \(b_1,b_2,\ldots, b_n\) аналогично.
У парикмахера есть \(m\) бритв. Каждая бритва имеет некоторый размер и может быть использована не более одного раза. За одну операцию парикмахер может выбрать одну бритву и обрезать с помощью нее отрезок волос Бориса. Формально, операция выглядит следующим образом:
- Выбрать ранее неиспользованную бритву, пусть ее размер равен \(x\);
- Выбрать отрезок \([l,r]\) (\(1\leq l \leq r \leq n\));
- Присвоить \(a_i := \min (a_i,x)\) для всех \(l\leq i \leq r\).
Обратите внимание, что некоторые бритвы могут иметь одинаковый размер. Парикмахер может выбирать размер \(x\) максимум столько раз, сколько у него есть бритв размера \(x\).
Парикмахер может выполнить сколько угодно операций, не используя одну бритву дважды. Необходимо, чтобы в конце выполнялось \(a_i = b_i\) для всех \(1 \leq i \leq n\). Он не обязан использовать все бритвы.
Определите, может ли парикмахер сделать необходимую Борису стрижку.
Выходные данные
Для каждого набора входных данных выведите «YES», если парикмахер может выполнить необходимую стрижку, и «NO» иначе.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом примере волосы Бориса изначально равны \([3,3,3]\). Опишем последовательность из \(2\) операций, которые может выполнить парикмахер:
- Использовать бритву размера \(1\) на отрезке \([2,2]\); волосы становятся \([3,1,3]\).
- Использовать бритву размера \(2\) на отрезке \([1,3]\); волосы становятся \([2,1,2]\), что и требуется.
В третьем примере можно ничего не делать, так как волосы уже в желаемом состоянии.
В четвертом примере нельзя обрезать волосы так, чтобы их длина увеличилась, и \([1,1,1]\) превратился в \([1,1,2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3
3 3 3
2 1 2
2
1 2
6
3 4 4 6 3 4
3 1 2 3 2 3
3
3 2 3
10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
3
1 1 1
1 1 2
12
4 2 4 3 1 5 6 3 5 6 2 1
13
7 9 4 5 3 3 3 6 8 10 3 2 5
5 3 1 5 3 2 2 5 8 5 1 1 5
8
1 5 3 5 4 2 3 1
13
7 9 4 5 3 3 3 6 8 10 3 2 5
5 3 1 5 3 2 2 5 8 5 1 1 5
7
1 5 3 4 2 3 1
3
19747843 2736467 938578397
2039844 2039844 2039844
1
2039844
|
YES
NO
YES
NO
YES
NO
YES
|