[语言月赛202303] M Function G

题目描述

对于一个长度为 $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)$ 的值。

样例 #1

样例输入 #1

10
3 72 26 91 5 84 18 29 50 23

样例输出 #1

11

提示

样例 1 解释

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

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$ | $\leq 10 ^ 9$ | 无 | | $8 \sim 10$ | $\leq 5 \times 10 ^ 5$ | $\leq 10 ^ 9$ | 无 | __________________________________________ 救救我救救我！！！ = ### 救命啊！！！ # 大佬们 本蒟蒻不会呀！！！！！！！！！！ =