После просмотра одного аниме перед сном Марку снится, что он стоит в старом классе с меловой доской, на которой записана последовательность из \(n\) положительных целых чисел \(a_1, a_2,\dots,a_n\).
Затем в класс заходит профессор Коро. Он может выполнять следующую операцию:
- выбрать целое число \(x\) которое присутствует на доске хотя бы \(2\) раза,
- стереть эти \(2\) вхождения,
- записать число \(x+1\) на доску.
После чего профессор Коро задает марку вопрос: «Какое максимально возможное число может появиться на доске после некоторого количества таких операций?»
Марк быстро отвечает на этот вопрос, но он всё ещё медленнее профессора Коро. Поэтому профессор Коро решает задать Марку дополнительные вопросы. Он будет менять изначальную последовательность чисел на доске \(q\) раз. Каждый раз он будет выбирать положительные целые числа \(k\) и \(l\), затем менять \(a_k\) на \(l\). После каждого такого изменения он будет спрашивать у Марка ответ на тот же самый вопрос.
Помогите Марку ответить на вопросы быстрее профессора Коро!
Обратите внимание, что изменения начальной последовательности на доске сохраняются. Изменения, внесенные в последовательность \(a\), будут так же применяться при обработке следующих изменений.
Выходные данные
Выведите \(q\) строк, \(i\)-я строка должна содержать единственное целое число — ответ после \(i\)-го изменения.
Примечание
В первом примере программа должна обработать \(4\) изменения.
После первого обновления последовательность на доске выглядит как \([2,3,2,4,5]\). Одна из возможных последовательностей операций, достигающих числа \(6\), такая:
- Изначально, на доске числа \([2,3,2,4,5]\).
- Удаляем два вхождения числа \(2\) и записываем \(3\), получая \([3,4,5,\color{red}{3}]\).
- Удаляем два вхождения числа \(3\) и записываем \(4\), получая \([4,5,\color{red}{4}]\).
- Удаляем два вхождения числа \(4\) и записываем \(5\), получая \([5,\color{red}{5}]\).
- Удаляем два вхождения числа \(5\) и записываем \(6\), получая \([\color{red}{6}]\).
Затем, во время второго изменения, массив станет равным \([2,3,2,4,3]\). В этот раз Марк не может достичь числа \(6\). Однако одна из последовательностей операций, приводящая к числу \(5\), такая:
- Изначально, на доске числа \([2,3,2,4,3]\).
- Удаляем два вхождения числа \(2\) и записываем \(3\), получая \([3,4,3,\color{red}{3}]\).
- Удаляем два вхождения числа \(3\) и записываем \(4\), получая \([3,4,\color{red}{4}]\).
- Удаляем два вхождения числа \(4\) и записываем \(5\), получая \([3,\color{red}{5}]\).
Во время третьего изменения массив станет равным \([2,3,2,1,3]\). Один из возможных вариантов достичь числа \(4\) такой:
- Изначально, на доске числа \([2,3,2,1,3]\).
- Удаляем два вхождения числа \(3\) и записываем \(4\), получая \([2,2,1,\color{red}{4}]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
2 2 2 4 5
2 3
5 3
4 1
1 4
|
6
5
4
5
|
|
2
|
2 1
200000 1
2 200000
|
200001
|