Задача A. Спираль ≡

Условие

Квадратная матрица размера n × n заполнена целыми числами от 1 до n² следующим образом.

• В левом верхнем углу находится число n².
• Остальные числа, начиная от n² − 1 вплоть до 1, располагаются в порядке убывания по спирали, закрученной по часовой стрелке.

Например, при n = 2 и n = 3 матрица принимает вид:

4 3        9 8 7
1 2        2 1 6
           3 4 5

Требуется по данному размеру матрицы n и номеру r вывести r-ю строку матрицы.

Формат входного файла

Входной файл содержит натуральные числа n r.

Формат выходного файла

Выходной файл должен содержать n чисел — r-ю строку матрицы.

Ограничения

1 ≤ r ≤ n ≤ 10⁵

Примеры тестов

2 1

4 3

3 2

2 1 6

4 3

6 1 2 11

Problem B. Lin-log sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

Задача C. Передовики производства ≡

Условие

На секретном оборонном заводе трудятся N рабочих. Каждый рабочий характеризуется своей производительностью — целым числом. С течением времени производительность некоторых рабочих может увеличиваться или уменьшаться. Вам задано число M — количество изменений производительности. Для каждого изменения известен номер рабочего, изменившего свою производительность и значение, на которое он она изменилась. Величина изменения может быть как положительной, так и отрицательной. Для планирования будущих достижений руководству завода необходимо всегда знать наибольшую производительность, достигнутую рабочими в данный момент.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 4
7 4 9 
2 3
1 4
2 10
2 -10

9
11
17
11

Задача D. Количество инверсий последовательнсти ≡

Условие

Пара элементов (A_i, A_j) последовательности A_N называется инверсией, если A_i > A_j и i < j.

Напишите программу, которая по заданной последовательности A_N посчитает количество инверсий.

Формат входного файла

В первой строке входного файла содержится число N — количество элементов последовательности

Последующие N целых чисел задают саму последовательность

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 10⁵

0 ≤ A_i ≤ 10⁹

Примеры тестов

7 1 2 5 9 13 16 20

0

9
1 1 2 3 8 6 1 9 9

5

Задача E. K-ая порядковая статистика ≡

Условие

K-ой порядковой статистикой N-элементной последовательности A_N называется число A_K, которое будет стоять на K-ом месте после упорядочивания элементов этой последовательности по возрастанию.

Последовательность A_N задаётся следующим образом. A₁ = P, A_i = (A_i − 1 ⋅ Q) mod V.

Формат входного файла

Во входном файле содержатся целые числа Q V P N K

Формат выходного файла

В выходном файле должно содержаться единственное число — K-ая порядковая статистика исходной последовательности.

Ограничения

V, Q ≠ 0

0 ≤ Q ⋅ V, Q ⋅ P ≤ 2³¹ − 1

1 ≤ K ≤ N ≤ 4 ⋅ 10⁷

Примеры тестов

343 32767 3 10 7

16478

Задача F. Финишные позиции ≡

Условие

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

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

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

Формат входного файла

Во входном файле содержится число N — количество элементов списка.

Далее следуют N чисел, задающие список.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 10⁶

Номера машин являются целыми неотрицательными числами, не превосходящими 10⁹

Примеры тестов

3
5 1 10

5 1 10

8
4 7 8 7 4 8 7 4

7 4 8

16
17 88 39 88 17 39 88 17 88 17 39 39 17 39 17 222222222

17 39 88 222222222

Задача G. Результаты квалификации ≡

Условие

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

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

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

Когда гонщик завершает очередной круг, в журнал записываются числа B_i и T_i — номер его машины и разность между временем, за которое он проехал этот круг, и текущим лучшим среди всех гонщиков временем. (T_i измеряется в тысячных долях секунды, T₁ всегда равно 0). Если T_i < 0, то время, показанное этим гонщиком, становится лучшим.

Требуется определить результат квалификации по записям в журнале.

Формат входного файла

Входной файл содержит число N — общее количество кругов, сделанных всеми гонщиками в квалификации.

Далее содержатся N пар целых чисел B_i T_i — записи в журнале в хронологическом порядке.

Формат выходного файла

Выходной файл должен содержать номера гоночных автомобилей, перечисленные в порядке расположения на старте гонки.

Ограничения

1 ≤ N ≤ 10⁵

Разница между лучшим и худшим временем не превышает 10⁹ тысячных секунды

1 ≤ B_i ≤ 10⁶

Примеры тестов

6
7
+0
2
+123
5
-11
2
+7
1
+0
3
+60200

5 1 2 7 3

Задача H. Хоттабыч и гирлянда ≡

Условие

Однажды под новый год Гассан Абдуррахман ибн Хоттаб решил помочь Вольке нарядить ёлку. Среди ёлочных украшений Хоттабычу больше всего понравилась гирлянда, состоящая из N цветных лампочек. Приглядевшись, Хоттабыч насчитал K различных цветов лампочек.

Хоттабыч вспомнил два своих любимых цвета, нашел пару ближайших друг к другу лампочек первого и второго цветов (порядок лампочек в паре не имеет значения), и подсчитал количество лампочек между ними. Потом он выбрал ещё два цвета и повторил поиск для них... Хоттабычу очень понравилось это занятие, и теперь он просит вас написать программу, которая, получив на входе описание гирлянды и M запросов Хоттабыча, отвечала бы на каждый запрос.

Рекомендуется рассмотреть частичные решения

• K ≤ 2
• N ≤ 100

Формат входного файла

В первой строке входного файла содержится число N.

В последующих N строчках содержатся цвета лампочек гирлянды.

В N + 2-й строке входного файла содержится число M.

В последующих 2 * M строчках содержатся запросы Хоттабыча (по две строки на запрос).

Формат выходного файла

Выходной файл должен содержать M чисел — ответы для каждого запроса в порядке поступления.

Если в запросе указан цвет, отсутствующий на гирлянде, то в качестве ответа следует вывести  − 1.

Если лампочки обоих цветов есть, но пару найти невозможно, следует вывести  − 2.

Ограничения

2 ≤ N ≤ 15000

1 ≤ M ≤ 20000

1 ≤ K ≤ 3000

Строка, задающая цвет, состоит из латинских букв, её длина не превышает 255 символов.

Примеры тестов

10
Red
Green
Blue
Red
Brown
Green
Yellow
Black
Green
Red
6
Red
Green
Blue
Brown
Yellow
Green
Red
Black
Black
Blue
Orange
Green

0
1
0
1
4
-1

10
B
C
D
F
G
E
R
C
A
G
3
C
G
R
B
E
E

1 5 -2