P12161 [蓝桥杯 2025 省 Java B] 研发资源分配

在蓝桥科技公司，$A$ 部门和 $B$ 部门正在竞争一种新型 AI 芯片的研发资源。 为了公平分配资源，公司设计了一个为期 $N$ 天的分配方案： 每天早上，$A$ 部门和 $B$ 部门各自提交一个需求等级（从 $1$ 到 $N$ 的整数）。提交等级较高的部门获得当天的资源，资源份额等于当天的日期编号（第 $1$ 天为 $1$ 单位，第 $2$ 天为 $2$ 单位，依次递增）。若两部门提交的等级相同，则当天资源作废，双方均无法获得资源。 每个部门必须在 $N$ 天内使用 $1$ 到 $N$ 的所有等级，且每个等级只能使用一次。 有趣的是，$A$ 部门在 $B$ 部门内部安插了一名 “间谍”，提前获知了 $B$ 部门的需求等级提交顺序，记为排列 ($P_1, P_2, \dots , P_N$)，其中 $P_i$ 表示 $B$ 部门在第 $i$ 天提交的需求等级。 现在，请你帮助 $A$ 部门分析，在已知 $B$ 部门需求等级顺序的情况下，$A$ 部门的总资源份额减去 $B$ 部门的总资源份额的差值最大可以是多少？

第一行包含一个整数 $N$，表示分配方案的天数。 第二行包含 $N$ 个整数 $P_1, P_2, \dots , P_N$，表示 $B$ 部门在第 $1$ 天到第 $N$ 天提交的需求等级。

输出一个整数，表示 $A$ 部门的总资源份额减去 $B$ 部门的总资源份额的最大差值。

### 样例说明 $A$ 部门可以选择排列 $[2, 1, 3]$： - 第 $1$ 天：$A(= 2) > B(= 1)$，$A$ 获得 $1$ 单位资源； - 第 $2$ 天：$A(= 1) < B(= 3)$，$B$ 获得 $2$ 单位资源； - 第 $3$ 天：$A(= 3) > B(= 2)$，$A$ 获得 $3$ 单位资源。 两者的差值为 $4 - 2 = 2$。 ### 评测用例规模与约定 - 对于 $20\%$ 的评测用例，$1 \leq N \leq 11$，$1 \leq P_i \leq N$，$P_1, P_2, \dots , P_N$ 各不相同。 - 对于 $100\%$ 的评测用例，$1 \leq N \leq 10^5$，$1 \leq P_i \leq N$，$P_1, P_2, \dots , P_N$ 各不相同。