I. Стек и очередь
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перед приемом к двум врачам выстроились $$$2$$$ очереди пациентов. Первый врач принимает пациентов в обычном порядке очереди — кто раньше пришел, того он раньше и примет. А второй врач делает наоборот — принимает сначала тех, кто пришел позже всех. То есть, к первому врачу стоит очередь, а ко второму — стек. Один пациент может одновременно стоять и в очереди, и в стеке. Каждый пациент характеризуется временем, которое займет его визит ко врачу (время одинаковое для обоих врачей).

Когда начнется прием, врачи будут принимать пациентов в порядке очереди и стека соответственно. Как только врач закончит с одним пациентом, он вызовет следующего.

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

Текущая конфигурация очереди и стека называется хорошей, если врачи могут принять всех пациентов, и при этом не возникнет неразбериха.

Изначально очередь и стек пусты. Поступают запросы трех типов:

  1. добавить пациента $$$x$$$ в очередь;
  2. добавить пациента $$$x$$$ в стек;
  3. пациент $$$x$$$, стоявший в очереди, понимает, что он стоит не туда и перемещается в стек; при этом он перемещается на то место в стеке, как если бы он встал в стек в момент запроса, когда он встал в очередь.

Гарантируется, что после каждого запроса каждый пациент занимает не более одного места в очереди и не более одного места в стеке.

После каждого запроса нужно узнать, является ли конфигурация хорошей.

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество запросов.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — для каждого пациента время, которое займет его визит ко врачу.

В каждой из следующих $$$n$$$ строк записаны два целых числа $$$t$$$ и $$$x$$$ ($$$1 \le t \le 3$$$; $$$1 \le x \le n$$$) — тип запроса и номер пациента. Гарантируется, что:

  • если запрос типа $$$1$$$, то пациент $$$x$$$ еще не стоит в очереди;
  • если запрос типа $$$2$$$, то пациент $$$x$$$ еще не стоит в стеке;
  • если запрос типа $$$3$$$, то пациент $$$x$$$ уже стоит в очереди и еще не стоит в стеке.
Выходные данные

После каждого запроса выведите «YES», если текущая конфигурация является хорошей, и «NO» в противном случае.

Примеры
Входные данные
3
10 15 4
1 1
2 1
2 2
Выходные данные
YES
NO
YES
Входные данные
7
2 5 1 5 5 4 8
1 1
2 5
1 2
2 3
3 2
1 2
3 1
Выходные данные
YES
YES
YES
YES
YES
NO
NO
Примечание

В первом тесте следующие конфигурации:

  1. очередь: $$$[1]$$$; стек: $$$[]$$$; пациента $$$1$$$ первый врач принимает $$$10$$$ минут, начиная с минуты $$$0$$$.
  2. очередь: $$$[1]$$$; стек: $$$[1]$$$; пациента $$$1$$$ первый врач принимает во время $$$[0; 10)$$$ и второй во время $$$[0; 10)$$$. Так как пациент $$$1$$$ должен одновременно быть у двух врачей, ответ «NO».
  3. очередь: $$$[1]$$$; стек: $$$[1, 2]$$$; пациента $$$1$$$ первый врач принимает во время $$$[0; 10)$$$, а второй во время $$$[15; 25)$$$; пациента $$$2$$$ второй врач принимает во время $$$[0, 15)$$$. Теперь пациент $$$1$$$ успевает ко второму врачу после приема у первого.

Во втором тесте конфигурации после запроса $$$4$$$ следующая конфигурация:

  • очередь: $$$[1, 2]$$$;
  • стек: $$$[5, 3]$$$;
  • пациент $$$1$$$: первый врач $$$[0, 2)$$$, второй врач не принимает;
  • пациент $$$2$$$: первый врач $$$[2, 7)$$$, второй врач не принимает;
  • пациент $$$3$$$: первый врач не принимает, второй врач $$$[0, 1)$$$;
  • пациент $$$5$$$: первый врач не принимает, второй врач $$$[1, 6)$$$.

После запроса $$$5$$$ следующая конфигурация:

  • очередь: $$$[1]$$$;
  • стек: $$$[5, 2, 3]$$$;
  • пациент $$$1$$$: первый врач $$$[0, 2)$$$, второй врач не принимает;
  • пациент $$$2$$$: первый врач не принимает, второй врач $$$[1, 6)$$$;
  • пациент $$$3$$$: первый врач не принимает, второй врач $$$[0, 1)$$$;
  • пациент $$$5$$$: первый врач не принимает, второй врач $$$[6, 11)$$$.

После запроса $$$6$$$ следующая конфигурация:

  • очередь: $$$[1, 2]$$$;
  • стек: $$$[5, 2, 3]$$$;
  • пациент $$$1$$$: первый врач $$$[0, 2)$$$, второй врач не принимает;
  • пациент $$$2$$$: первый врач $$$[2, 7)$$$, второй врач $$$[1, 6)$$$;
  • пациент $$$3$$$: первый врач не принимает, второй врач $$$[0, 1)$$$;
  • пациент $$$5$$$: первый врач не принимает, второй врач $$$[6, 11)$$$.

Пациент $$$2$$$ должен быть у двух врачей одновременно.

После запроса $$$7$$$ следующая конфигурация:

  • очередь: $$$[2]$$$;
  • стек: $$$[1, 5, 2, 3]$$$;
  • пациент $$$1$$$: первый врач не принимает, второй врач $$$[11, 13)$$$;
  • пациент $$$2$$$: первый врач $$$[0, 5)$$$, второй врач $$$[1, 6)$$$;
  • пациент $$$3$$$: первый врач не принимает, второй врач $$$[0, 1)$$$;
  • пациент $$$5$$$: первый врач не принимает, второй врач $$$[6, 11)$$$.

Пациент $$$2$$$ должен быть у двух врачей одновременно.