Вам дано мультимножество \(S\), изначально состоящее из \(n\) различных неотрицательных целых чисел. Мультимножество это множество, которое может содержать некоторые элементы несколько раз.
Вы должны выполнить следующую операцию \(k\) раз:
- Добавить число \(\lceil\frac{a+b}{2}\rceil\) (округление вверх) в \(S\), где \(a = \operatorname{mex}(S)\), а \(b = \max(S)\). Если это число уже присутствует во множестве, добавьте его еще раз.
Здесь \(\operatorname{max}\) мультимножества обозначает максимальный элемент в этом мультимножестве, а \(\operatorname{mex}\) мультимножества обозначает минимальное неотрицательное число, которое не лежит в этом мультимножестве. Например,
- \(\operatorname{mex}(\{1,4,0,2\})=3\);
- \(\operatorname{mex}(\{2,5,1\})=0\).
Ваша задача — вычислить количество различных элементов в \(S\) после выполнения \(k\) операций.
Выходные данные
Для каждого набора входных данных выведите количество различных элементов в \(S\) после выполнения \(k\) операций.
Примечание
В первом наборе входных данных \(S=\{0,1,3,4\}\), \(a=\operatorname{mex}(S)=2\), \(b=\max(S)=4\), \(\lceil\frac{a+b}{2}\rceil=3\). Поэтому в \(S\) добавляется число \(3\), а \(S\) становится равным \(\{0,1,3,3,4\}\). Таким образом, ответ равен \(4\).
Во втором наборе входных данных \(S=\{0,1,4\}\), \(a=\operatorname{mex}(S)=2\), \(b=\max(S)=4\), \(\lceil\frac{a+b}{2}\rceil=3\). Поэтому в \(S\) добавляется число \(3\), а \(S\) становится равным \(\{0,1,3,4\}\). Таким образом, ответ равен \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 1
0 1 3 4
3 1
0 1 4
3 0
0 1 4
3 2
0 1 2
3 2
1 2 3
|
4
4
3
5
3
|