[JRKSJ R5] Jalapeno and Garlic
题目背景
题目描述
一个 $n$ 个点的环，点有点权 $a$，编号依次从 $1\sim n$。点 $1$ 与点 $n$ 相邻。
你希望只存在一个 $x\in[1,n]$ 满足 $a_x\ne 0$。为此，你需要按下面流程进行操作：
1. 选定一个 $x$，表示最终使得 $a_x\ne 0$。**此后不能更改 $x$ 的选择。**
2. 进行若干次修改操作，每次操作你可以选定一个 $y\in[1,n]$，将 $a_y\gets a_y-1$。同时在与点 $y$ 相邻的两个点中**等概率选择**一个，其点权将被 $+1$。
你希望期望的修改次数最少，所以求在最优策略下的期望操作次数（操作 1 不计入）。
输入输出格式
输入格式
第一行一个整数 $n$。\
第二行 $n$ 个整数表示 $a_{1\dots n}$。
输出格式
一个整数，表示答案。输出时答案对 $1004535809$ 取模。
输入输出样例
输入样例 #1
2
114514 1919810输出样例 #1
114514输入样例 #2
3
1 1 2输出样例 #2
4说明
### 样例 $1$ 解释
选定 $x=2$，进行 $114514$ 次操作，每次的 $y=1$。
### 数据规模
**本题采用捆绑测试。**
| $\text{Subtask}$ | $n\le$ |分值 |
| :----------: | :----------: |:----------: |
| $1$ | $2$ | $5$ |
| $2$ | $10^3$ | $20$ |
| $3$ | $10^4$ | $20$ |
| $4$ | $10^5$ | $20$ |
| $5$ | $10^6$ | $35$ |
对于 $100\%$ 的数据，$2\le n\le 10^6$，$0\le a_i<1004535809$。