D. Сине-красная перестановка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив целых чисел $$$a$$$ длины $$$n$$$. Элементы массива могут быть как различными, так и одинаковыми.

Каждый элемент массива покрашен либо в синий цвет, либо в красный. Непокрашенных элементов в массиве нет. За один ход разрешается применить к массиву одну из двух описанных ниже операций:

  • либо выбрать любой синий элемент и уменьшить его значение на $$$1$$$;
  • либо выбрать любой красный элемент и увеличить его значение на $$$1$$$.

Допустимы ситуации, в которых элементов некоторого цвета нет вообще. Например, если весь массив целиком покрашен в синий, или, наоборот, в красный. В таком случае первый (или второй, соответственно) способ сделать ход недоступен.

Определите, можно ли сделать $$$0$$$ или более ходов так, чтобы в результате массив стал перестановкой чисел от $$$1$$$ до $$$n$$$?

Иными словами, проверьте существует ли такая последовательность ходов (возможно, пустая), что после её применения массив $$$a$$$ содержит в некотором порядке все числа от $$$1$$$ до $$$n$$$ (включительно), каждое ровно по одному разу.

Входные данные

В первой строке записано целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных в тесте.

Описание каждого набора входных данных состоит из трех строк. В первой строке содержится целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина исходного массива $$$a$$$. Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — сами элементы массива.

Третья строка имеет длину $$$n$$$ и состоит исключительно из букв 'B' и/или 'R': $$$i$$$-й символ равен 'B', если $$$a_i$$$ покрашен в синий цвет, и равен 'R', если в красный.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите YES, если соответствующий массив можно превратить в перестановку, и NO в противном случае.

Вы можете выводить ответ в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).

Пример
Входные данные
8
4
1 2 5 2
BRBR
2
1 1
BB
5
3 1 4 2 5
RBRRB
5
3 1 3 1 3
RBRRB
5
5 1 5 1 5
RBRRB
4
2 2 2 2
BRBR
2
1 -2
BR
4
-2 -1 4 0
RRRR
Выходные данные
YES
NO
YES
YES
NO
YES
YES
YES
Примечание

В первом наборе входных данных примера можно выполнить следующую последовательность ходов:

  • выбрать $$$i=3$$$, элемент $$$a_3=5$$$ синий, поэтому уменьшим его, получим $$$a=[1,2,4,2]$$$;
  • выбрать $$$i=2$$$, элемент $$$a_2=2$$$ красный, поэтому увеличим его, получим $$$a=[1,3,4,2]$$$;
  • выбрать $$$i=3$$$, элемент $$$a_3=4$$$ синий, поэтому уменьшим его, получим $$$a=[1,3,3,2]$$$;
  • выбрать $$$i=2$$$, элемент $$$a_2=2$$$ красный, поэтому увеличим его, получим $$$a=[1,4,3,2]$$$.

Получили, что $$$a$$$ — перестановка. Следовательно, ответ YES.