CF623B Array GCD

给定一个长度为 $n$ 的数组 $a_{i}$。你可以依次对该数组执行以下两种操作： - 移除一个长度为 $m < n$ 的子段（连续子序列），并为此支付 $m·a$ 个金币； - 将数组中的某些元素修改至多 $1$（即增加或减少 $1$），每修改一个元素需支付 $b$ 个金币。 请注意，每种操作最多只能执行一次（也可以不执行），因此只能移除一个子段，每个数最多只能改变 $1$。另外，不能删除整个数组。 你的目标是计算，为了使最终数组所有元素的最大公约数大于 $1$，所需支付的最小金币数。

输入的第一行包含三个整数 $n$、$a$ 和 $b$（$1 \leq n \leq 1000000, 0 \leq a, b \leq 10^{9}$）——数组长度，移除一个元素的代价，以及修改一个元素的代价。 第二行包含 $n$ 个整数 $a_{i}$（$2 \leq a_{i} \leq 10^{9}$）——数组中的元素。

输出一个整数，表示将数组修改为所有元素的最大公约数大于 $1$ 所需的最小花费。

在第一个样例中，最优做法是移除数字 $3$，花费 $1$ 个金币。 在第二个样例中，你需要移除一个子段 $[17,13]$，然后将数字 $6$ 减少 $1$。这些变动的总花费为 $2·3+2=8$ 个金币。 由 ChatGPT 5 翻译