P16798 [蓝桥杯 2026 国 B] Token 词元

2026 年 3 月，全国科学技术名词审定委员会发布公告，优先将人工智能领域术语“Token”的中文译名定为“词元”，并面向全社会试用。从那时起，小蓝所在的平台开始以“词元”作为月度统计的正式单位。 平台上共有 $n$ 个接口，按从左到右的顺序编号为 $1$ 到 $n$，其中第 $i$ 个接口本月累计消耗的词元数量为 $p_i$。 月末，平台需要根据词元消耗为每个接口安排下月的巡检等级。每个接口都会被分配一个正整数巡检等级，巡检等级越高，表示该接口需要被更重点地观察。不过，平台并不直接根据词元数量的绝对大小来分配巡检等级，而是参考相邻接口之间的相对关系。 对第 $i$ 个接口，定义 $c_i$ 为与它相邻的接口中，消耗词元数量小于 $p_i$ 的接口个数。这里的相邻接口指编号相差 $1$ 的接口，即接口 $i$ 只可能与接口 $i-1$ 和接口 $i+1$ 相邻；编号为 $1$ 的接口仅存在右侧相邻接口，编号为 $n$ 的接口仅存在左侧相邻接口，其余接口均有左右两个相邻接口。因此 $c_i \in \{0, 1, 2\}$。 设第 $i$ 个接口的巡检等级为 $a_i$。平台要求任意相邻接口 $i$ 与 $i+1$ 满足： - 若 $c_i < c_{i+1}$，则 $a_i < a_{i+1}$； - 若 $c_i > c_{i+1}$，则 $a_i > a_{i+1}$； - 若 $c_i = c_{i+1}$，则 $a_i$ 与 $a_{i+1}$ 的大小关系不作要求。 满足规则的巡检等级分配方案可能有多种。由于巡检资源有限，平台希望巡检等级总和最小（即最小化 $\sum_{i=1}^{n} a_i$）。 现在，请你帮助平台求出这个最小值。

输入共两行。 第一行包含一个正整数 $n$，表示接口的数量。 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$，其中 $p_i$ 表示第 $i$ 个接口本月消耗的词元数量。

输出一行，包含一个正整数，表示在满足所有相邻接口巡检等级要求的前提下，所有接口巡检等级之和的最小值。

### 【评测用例规模与约定】 对于 $30\%$ 的评测用例，$2 \le n \le 2 \times 10^3$，$1 \le p_i \le 10^5$； 对于所有评测用例，$2 \le n \le 2 \times 10^5$，$1 \le p_i \le 10^9$。