题目描述

Maximizer 有两个排列 $A=[a_1,a_2,\cdots,a_N]$ 和 $B=[b_1,b_2,\cdots,b_N]$。$A$ 和 $B$ 的长度均为 $N$，且都由 $1$ 到 $N$ 的 互不相同的整数 组成。

Maximizer 想要最大化每个元素差值的和，即 $\sum_{i=1}^{N} |a_i - b_i|$。但他只能交换 $A$ 中相邻的两个元素。具体来说，他只能交换 $a_i$ 和 $a_{i+1}$，其中 $i$ 从 $1$ 到 $N-1$。他可以进行任意多次交换。

为了最大化差值之和，所需的最小交换次数是多少？

输入格式

第一行包含一个整数 $N$（$1 \leq N \leq 250,000$）。

第二行包含 $N$ 个整数 $a_1,a_2,\cdots,a_N$（$1 \leq a_i \leq N$）。

第三行包含 $N$ 个整数 $b_1,b_2,\cdots,b_N$（$1 \leq b_i \leq N$）。

$[a_1,a_2,\cdots,a_N]$ 和 $[b_1,b_2,\cdots,b_N]$ 都是排列。换句话说，它们都由 $1$ 到 $N$ 的互不相同的整数组成。

输出格式

输出一个整数，表示为了最大化差值之和所需的最小交换次数。

3
1 2 3
1 2 3

2

4
3 4 1 2
3 2 4 1

3

提示

翻译由 DeepSeek V3 完成