题目描述

对于一个长度为 $n$ 的正整数数列 $a$，Farmer John 定义 M 函数 $M(l, r)$ 如下：

$$M(l, r) = \begin{cases} \left(M(l, \left \lfloor \dfrac{l + r}{2} \right \rfloor) \bmod \max(M(\left \lfloor \dfrac{l + r}{2} \right \rfloor + 1, r), 7)\right ) + \left(a _ {\left \lfloor \frac{l + r}{2} \right \rfloor} - 1 \right ) & |r - l| > 5 \\ \max \limits _ {l \leq i \leq r}{a _ i} & |r - l| \leq 5 \end{cases} $$

$\max \limits _ {l \leq i \leq r}{a _ i}$ 代表 $a _ l, a _ {l + 1}, \cdots, a _ {r - 1}, a _ r$ 中的最大值。

$\left \lfloor x \right \rfloor$ 代表 $\leq x$ 的最大整数。比如 $\left \lfloor 4.2 \right \rfloor = 4$，$\left \lfloor 5 \right \rfloor = 5$。

$\max(x, y)$ 代表 $x, y$ 中的最大值。

现在给定 $n$ 和 $a$，请你求出 $M(1, n)$。

输入格式

输入共两行。

第一行为一个整数 $n$。

第二行为 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，对应题目中的正整数数列 $a$。

输出格式

输出共一行一个整数，代表 $M(1, n)$ 的值。

10
3 72 26 91 5 84 18 29 50 23

11

提示

样例 1 解释

我们这里暂时使用 $\max \{a _ l, a _ {l + 1}, \cdots, a _ r\}$ 来表示 $a _ l, a _ {l + 1}, \cdots, a _ r$ 中的最大值。

$$\begin{aligned} M(1, 10) &= M(1, 5) \bmod \max(M(6, 10), 7) + (a _ 5 - 1) \\ &= \max \{a _ 1, a _ 2 \cdots, a _ 5\} \bmod \max(\max \{a _ 6, a _ 7 \cdots, a _ {10}\}, 7) + (a _ 5 - 1) \\ &= \max \{a _ 1, a _ 2 \cdots, a _ 5\} \bmod \max(84, 7) + (a _ 5 - 1) \\ &= \max \{a _ 1, a _ 2 \cdots, a _ 5\} \bmod 84 + (a _ 5 - 1) \\ &= 91 \bmod 84 + (a _ 5 - 1) \\ &= 7 + (a _ 5 - 1) \\ &= 11 \end{aligned}$$

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n \leq 5 \times 10 ^ 5$，$1 \leq a _ i \leq 10 ^ 9$。

测试点编号	$n$	$a _ i$	特殊性质
$1 \sim 2$	$\leq 10$	$\leq 100$	无
$3 \sim 5$	$\leq 10 ^ 3$	$\leq 10 ^ 4$
$6$	$\leq 5 \times 10 ^ 5$	$\leq 10 ^ 9$	$a _ i = 1$
$7$	$= 5$		无
$8 \sim 10$	$\leq 5 \times 10 ^ 5$