题目背景

题目描述

一个 $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$ 取模。

2
114514 1919810

114514

3
1 1 2

4

提示

样例 $1$ 解释

选定 $x=2$，进行 $114514$ 次操作，每次的 $y=1$。

数据规模

本题采用捆绑测试。

对于 $100\%$ 的数据，$2\le n\le 10^6$，$0\le a_i<1004535809$。