Олимпиадный тренинг

Задача . F. Джокер


Задача

Темы: жадные алгоритмы математика Перебор реализация *2000

Рассмотрим колоду из \(n\) карт. Позиции в колоде пронумерованы от \(1\) до \(n\) сверху вниз. На \(m\)-й позиции расположен джокер.

К колоде последовательно применяются \(q\) операций. Во время \(i\)-й операции необходимо взять карту на \(a_i\)-й позиции и переместить её либо в начало, либо в конец колоды. Например, если колода имеет вид \([2, 1, 3, 5, 4]\), и \(a_i=2\), то после операции колода будет \([1, 2, 3, 5, 4]\) (карту со второй позиции перенесли в начало) или \([2, 3, 5, 4, 1]\) (карту со второй позиции перенесли в конец).

Ваша задача — посчитать количество различных позиций, в которых может находиться джокер после каждой из операций.

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

Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа \(n\), \(m\) и \(q\) (\(2 \le n \le 10^9\); \(1 \le m \le n\); \(1 \le q \le 2 \cdot 10^5\)).

Вторая строка содержит \(q\) целых чисел \(a_1, a_2, \dots, a_q\) (\(1 \le a_i \le n\)).

Дополнительное ограничение на входные данные: сумма \(q\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\).

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

Для каждого набора входных данных выведите \(q\) целых чисел — количество различных позиций, в которых может находиться джокер после каждой из операций.


Примеры
№Входные данныеВыходные данные
1 5
6 5 3
1 2 3
2 1 4
2 1 1 2
5 3 1
3
3 2 4
2 1 1 1
18 15 4
13 15 1 16 
2 3 5 
2 2 2 2 
2 
2 3 3 3 
2 4 6 8

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет