Это простая версия задачи. Различия между версиями заключаются в ограничениях на \(n\) и сумму \(n\). В этой версии \(n \leq 3000\), а сумма \(n\) не превосходит \(10^4\). Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Так-так-так, посмотрим, как Бесси распоряжается своими финансами. Похоже, она в финансовой яме! К счастью, чтобы решить эту проблему, она устраивается на работу в Moogle. Собеседования в Moogle требуют глубокого знания непонятных алгоритмов и сложных структур данных, но Бесси получила от легендарного гроссмейстера наводку на то, что именно ей нужно изучить.
Бесси написала следующий код для бинарного поиска определенного элемента \(k\) в возможно несортированном массиве \([a_1, a_2,\ldots,a_n]\) с \(n\) элементами.
let l = 1
let h = n
while l < h:
let m = floor((l + h) / 2)
if a[m] < k:
l = m + 1
else:
h = m
return l
Бесси отправила свой код в задачу фермера Джона с \(m\) (\(1 \leq m \leq n\)) тестами. \(i\)-й тест имеет вид \((x_i, k_i)\) (\(1 \leq x, k \leq n\)). Гарантируется, что все \(x_i\) различны и все \(k_i\) различны.
Тест \(i\) корректен, если выполняются следующие условия:
- \(x_i\)-й элемент в массиве — \(k_i\).
- Если Бесси вызовет двоичный поиск, как показано в коде выше, для \(k_i\), то он вернет \(x_i\).
Возможно, не все \(m\) тестов будут корректны на одном и том же массиве, поэтому фермер Джон удалит некоторые из них, чтобы Бесси могла пройти все тесты. Пусть \(r\) — это минимальное количество тестов, которое нужно удалить, чтобы существовал массив \([a_1, a_2,\ldots,a_n]\), в котором \(1 \leq a_i \leq n\), чтобы все оставшиеся тесты были корректными.
Помимо нахождения \(r\), фермер Джон хочет, чтобы вы подсчитали количество массивов \([a_1, a_2,\ldots,a_n]\), в которых \(1 \leq a_i \leq n\), таких, что существует способ удалить ровно \(r\) тестов так, чтобы все оставшиеся тесты были корректными. Поскольку это число может быть очень большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите два целых числа: \(r\) — минимальное количество удаленных тестов, чтобы существовал массив, в котором все оставшиеся тесты корректны; и количество массивов, для которых можно удалить \(r\) тестов, чтобы все оставшиеся тесты были корректны, по модулю \(998\,244\,353\).
Примечание
Рассмотрим первый пример.
В первом наборе входных данных массив \([1,2,2,3,4]\) удовлетворяет всем \(m\) тестам, поэтому минимальное количество тестов, которые должна удалить Бесси, равно \(0\). Обратите внимание, что это также единственный массив, который удовлетворяет всем \(m\) тестам.
Во втором наборе входных данных минимальное количество тестов, которое Бесси должна удалить, равняется \(1\). Единственный тест, который Бесси может удалить, это \((2,5)\). Если Бесси удалит тест \((2,5)\), то массивами, удовлетворяющими оставшимся \(m-1\) тестам, будут \([2,2,3,1,4]\), \([2,2,3,2,4]\), \([2,2,3,3,4]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 4
1 1
2 2
4 3
5 4
5 4
5 4
2 5
1 2
3 3
|
0 1
1 3
|
|
2
|
2
6 6
1 3
2 5
3 1
4 2
5 4
6 6
30 8
19 22
6 12
12 1
28 27
3 4
14 25
29 14
11 15
|
3 78
3 839271911
|