Вам даны два массива чисел длины $$$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$$$ баллов.
21 32 4
4 1
310 15 67 12 14
18 2
21 71000000000 998244353
1998244345 2
582 494 27 39390 99999999983 495 28 39391 1000000000
2000078561 12
810 20 30 40 50 60 70 8032 33 34 35 36 37 38 39
184 720
Рассмотрим первый пример. Всего есть $$$2$$$ перестановки длины $$$2$$$:
Максимальный счёт равен $$$4$$$, и он достигается только на одной перестановке.
Рассмотрим второй пример. Всего есть $$$6$$$ перестановок длины $$$3$$$:
Максимальный счёт равен $$$18$$$, и есть $$$2$$$ перестановки, на которых достигается этот счёт.