Ваня придумал интересный фокус с множеством целых чисел.
Пусть у фокусника есть множество положительных целых чисел \(S\). Он называет некоторое положительное целое число \(x\). Зритель должен выбрать, не показывая фокуснику, некоторое подмножество \(S\) (возможно пустое). После этого зритель называет фокуснику размер выбранного подмножества. Фокус заключается в том, что после этого фокусник отгадывает: верно ли, что сумма элементов выбранного подмножества не превосходит \(x\). Для пустого подмножества сумма предполагается равной \(0\).
Ване очень понравился этот фокус, поэтому он начал готовиться к тому, чтобы показать его публике. Для этого он приготовил некоторое множество различных положительных целых чисел \(S\). Конечно, Ваня хочет, чтобы фокус обязательно получился. Он называет положительное целое число \(x\) неудачным, если не может быть точно уверен, что фокус пройдет удачно для любого подмножества, которое выберет зритель.
Чтобы оценить, насколько хорошее множество \(S\) он выбрал, он хочет посчитать количество неудачных положительных целых чисел для него.
Также Ваня планирует протестировать различные множества \(S\). Поэтому он просит вас написать программу, которая найдет количество неудачных положительных целых чисел для изначального множества \(S\) и для множества \(S\) после каждого изменения. Ваня сделает \(q\) изменений своего множества, каждое изменение будет одного из двух видов:
- Добавить новое число \(a\) в множество \(S\).
- Удалить некоторое число \(a\) из множества \(S\).
Выходные данные
Выведите \(q + 1\) строку.
В первой строке выведите количество неудачных положительных целых чисел для изначального множества \(S\). В следующих \(q\) строках выведите количество неудачных положительных чисел для множества \(S\) после каждого изменения.
Примечание
В первом тесте изначальное \(S = \{1, 2, 3\}\). Для этого множества фокус может не получиться при \(x \in \{1, 2, 3, 4\}\). Например, если \(x = 4\), то зритель может загадать подмножество \(\{1, 2\}\), сумма элементов которого равна \(3 \leq x\), а может загадать подмножество \(\{2, 3\}\), сумма элементов которого равна \(5 > x\). Однако в обоих случаях зритель назовет фокуснику размер подмножества \(2\), поэтому он не сможет точно сделать правильный ответ. При этом поскольку подмножество размера \(3\) единственно, а сумма в любом подмножестве меньшего размера не превосходит \(5\), все \(x \ge 5\) не являются неудачными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 11
1 2 3
2 1
1 5
1 6
1 7
2 6
2 2
2 3
1 10
2 5
2 7
2 10
|
4
1
6
12
19
13
8
2
10
3
0
0
|