У Tokitsukaze есть две красочные ленты. Существует \(n\) различных цветов, пронумерованных от \(1\) до \(n\), и каждый цвет появляется ровно один раз на каждой из двух лент. Обозначим цвет \(i\)-й позиции первой ленты как \(ca_i\), а цвет \(i\)-й позиции второй ленты как \(cb_i\).
Теперь Tokitsukaze хочет выбрать для каждого цвета некоторое целочисленное значение от \(1\) до \(n\), различные для всех цветов. После этого она запишет во все позиции на каждой ленте значение соответствующего цвета. Обозначим число, записанное в \(i\)-й позиции первой ленты как \(numa_i\), а число в \(i\)-й позиции второй ленты как \(numb_i\).
В примере на рисунке выше, если предположить, что красный цвет получит значение \(x\) (\(1 \leq x \leq n\)), то так как он появляется на \(1\)-й позиции первой ленты и на \(3\)-й позиции второй ленты, то \(numa_1=numb_3=x\).
Обратите внимание, что все цвета \(i\) от \(1\) до \(n\) будут иметь различные значения, и один и тот же цвет, встречающийся в обеих лентах, будет иметь одинаковое значение.
После выбора значений цветов красота двух лент рассчитывается как \(\)\sum_{i=1}^{n}|numa_i-numb_i|.\(\)
Пожалуйста, помогите Tokitsukaze найти самую высокую возможную красоту лент.
Выходные данные
Для каждого набора входных данных выведите одно целое число — наибольшую возможную красоту.
Примечание
Оптимальное решение для первого набора входных данных показано на следующем рисунке:
Красота равна \(\left|4-3 \right|+\left|3-5 \right|+\left|2-4 \right|+\left|5-2 \right|+\left|1-6 \right|+\left|6-1 \right|=18\).
Оптимальное решение для второго набора входных данных показано на следующем рисунке:
Красота равна \(\left|2-2 \right|+\left|1-6 \right|+\left|3-3 \right|+\left|6-1 \right|+\left|4-4 \right|+\left|5-5 \right|=10\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
1 5 4 3 2 6
5 3 1 4 6 2
6
3 5 4 6 2 1
3 6 4 5 2 1
1
1
1
|
18
10
0
|