Крайний банк занимается важной деятельностью — контролем биржей бипок и обнаружением потенциального мошенничества. Вам, как стажеру Крайнего Банка, поручили разработать систему, которая позволяла бы определять, является ли данный трейдер потенциальным мошенником или нет. Вы знаете, что биржа бипок работала $$$n$$$ моментов времени, в течение которых трейдер торговал на бирже.
Вам известно, что в $$$i$$$-й момент времени цена одной бипки составляла $$$a_i$$$ и трейдер продал или купил $$$|b_i|$$$ бипок по данной цене. Если $$$b_i < 0$$$, то он продал $$$-b_i$$$ бипок, а если $$$b_i > 0$$$, то купил $$$b_i$$$ бипок. На момент начала торгов у трейдера было $$$0$$$ бипок, а также известно, что к концу торгов он распродал все бипки (другими словами, сумма $$$b_i$$$ равна $$$0$$$). Также трейдер не мог уходить в минус, то есть в любой момент времени у него было неотрицательное количество бипок. Если $$$b_i = 0$$$, то в $$$i$$$-й день трейдер не продавал и не покупал бипки.
Крайний банк считает трейдера потенциальным мошенником, если каждой операции покупки одной конкретной бипки можно сопоставить в пару операцию продажи одной бипки так, что покупка произошла раньше продажи и стоимость покупки строго меньше стоимости продажи. Обратите внимание, что разным операциям покупки одной бипки должны соответствовать разные операции продажи. При этом, если две бипки были куплены в один и тот же момент времени, операции продажи для них могли произойти в разное время.
Определите, является ли данный трейдер потенциальным мошенником.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 200\,000$$$) — количество моментов времени, в течение которых трейдер торговал на бирже.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — стоимость одной бипки в $$$i$$$-й момент времени.
Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \leq b_i \leq 10^9$$$) — числа, характеризующие операции покупки/продажи, совершенные трейдером, в соответствии с форматом, описанным в условии.
Гарантируется, что в любой момент времени у трейдера было неотрицательное количество бипок, а также $$$b_1 + b_2 + \ldots + b_n = 0$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.
Для каждого набора входных данных выведите «Yes» (без кавычек), если трейдер является потенциальным мошенником, иначе выведите «No» (без кавычек).
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
В данной задаче $$$25$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$4$$$ балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Обозначим за $$$N$$$ сумму $$$n$$$ по всем наборам входных данных в данном тесте.
Решения, корректно работающие при $$$n \leq 7$$$, $$$t \leq 10$$$, наберут не менее $$$24$$$ баллов.
Решения, корректно работающие при $$$N \leq 3000$$$, наберут не менее $$$60$$$ баллов.
Решения, корректно работающие при $$$a_i \leq 3$$$, наберут не менее $$$28$$$ баллов.
432 3 21 1 -232 3 41 1 -252 3 3 3 41 1 -1 1 -221000000000 10000000001000000000 -1000000000
No Yes Yes No
В первом наборе входных данных трейдер продает бипки, купленные по цене $$$2$$$ и $$$3$$$ по цене $$$2$$$. Тем самым он не выходит в плюс по каждой бипке и не является потенциальным мошенником.
Во втором наборе входных данных трейдер продает бипки, купленные по цене $$$2$$$ и $$$3$$$ по цене $$$4$$$. Тем самым он выходит в плюс по каждой бипке и является потенциальным мошенником.
В третьем наборе входных данных трейдер может продать в третий момент времени бипку, купленную по цене $$$2$$$ за $$$3$$$ и выйти по ней в плюс. После чего в пятый момент времени продать все остальные бипки и выйти по ним в плюс. Таким образом, он является потенциальным мошенником.