Максимальная попарная разница
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два массива чисел длины $$$n$$$: $$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_n$$$. При этом известно, что все числа $$$a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$$$ попарно различны.

Назовём счётом перестановки $$$p_1, p_2, \ldots, p_n$$$ длины $$$n$$$ значение следующего выражения: $$$\lvert a_1 - b_{p_1} \rvert + \lvert a_2 - b_{p_2} \rvert + \ldots + \lvert a_n - b_{p_n} \rvert$$$.

Вам нужно найти максимально возможный счёт по всем перестановкам длины $$$n$$$, а также количество перестановок длины $$$n$$$, имеющих этот максимальный счёт. Так как количество перестановок может быть достаточно большим, требуется найти только его остаток при делении на $$$10^9 + 7$$$. Обратите внимание, что от самого максимально возможного счёта не нужно брать остаток.

Напомним, что перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 50\,000$$$) — длина массивов $$$a$$$ и $$$b$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — элементы массива $$$b$$$.

Гарантируется, что все числа $$$a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$$$ попарно различны. То есть, для любых $$$1 \le i, j \le n$$$ верно, что $$$a_i \neq b_j$$$, а также $$$a_i \ne a_j$$$ и $$$b_i \ne b_j$$$ при $$$i \ne j$$$.

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

Выведите два целых числа — максимально возможный счёт и количество перестановок с этим счётом. Количество перестановок выведите по модулю $$$10^9 + 7$$$. От самого максимально возможного счёта не нужно брать остаток.

Система оценки

В данной задаче $$$50$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$2$$$ балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$n \leq 10$$$, наберут не менее $$$16$$$ баллов.

Решения, корректно работающие при $$$n \leq 18$$$, наберут не менее $$$30$$$ баллов.

Решения, корректно работающие при $$$n \leq 1000$$$, наберут не менее $$$50$$$ баллов.

Дополнительно, решения, корректно работающие при $$$b_i = a_i+1$$$ для всех $$$1 \leq i \leq n$$$, наберут не менее $$$14$$$ баллов.

Дополнительно, решения, корректно работающие при $$$b_{i+1}=b_i+1$$$ для всех $$$1 \leq i < n$$$, наберут не менее $$$14$$$ баллов.

Примеры

Входные данные
2
1 3
2 4
Выходные данные
4 1
Входные данные
3
10 15 6
7 12 14
Выходные данные
18 2
Входные данные
2
1 7
1000000000 998244353
Выходные данные
1998244345 2
Входные данные
5
82 494 27 39390 999999999
83 495 28 39391 1000000000
Выходные данные
2000078561 12
Входные данные
8
10 20 30 40 50 60 70 80
32 33 34 35 36 37 38 39
Выходные данные
184 720

Примечание

Рассмотрим первый пример. Всего есть $$$2$$$ перестановки длины $$$2$$$:

  1. $$$p = [1, 2]$$$. Счёт перестановки равен $$$|a_1 - b_1| + |a_2 - b_2| = |1 - 2| + |3 - 4| = 2$$$.

  2. $$$p = [2, 1]$$$. Счёт перестановки равен $$$|a_1 - b_2| + |a_2 - b_1| = |1 - 4| + |3 - 2| = 4$$$.

    Максимальный счёт равен $$$4$$$, и он достигается только на одной перестановке.

Рассмотрим второй пример. Всего есть $$$6$$$ перестановок длины $$$3$$$:

  1. $$$p = [1, 2, 3]$$$. Счёт перестановки равен $$$|10 - 7| + |15 - 12| + |6 - 14| = 14$$$.

  2. $$$p = [1, 3, 2]$$$. Счёт перестановки равен $$$|10 - 7| + |15 - 14| + |6 - 12| = 10$$$.

  3. $$$p = [2, 1, 3]$$$. Счёт перестановки равен $$$|10 - 12| + |15 - 7| + |6 - 14| = 18$$$.

  4. $$$p = [2, 3, 1]$$$. Счёт перестановки равен $$$|10 - 12| + |15 - 14| + |6 - 7| = 4$$$.

  5. $$$p = [3, 1, 2]$$$. Счёт перестановки равен $$$|10 - 14| + |15 - 7| + |6 - 12| = 18$$$.

  6. $$$p = [3, 2, 1]$$$. Счёт перестановки равен $$$|10 - 14| + |15 - 12| + |6 - 7| = 8$$$.

Максимальный счёт равен $$$18$$$, и есть $$$2$$$ перестановки, на которых достигается этот счёт.