Farmer John's M Function

You are given a sequence of n positive integers \(a_1, a_2, \dots, a_n\). Farmer John defines a recursive function \(M(l, r)\) for any segment \([l, r]\) (1-indexed) as follows:

[ M(l, r)=\begin{cases} \left(M\Big(l,\left\lfloor \dfrac{l+r}{2} \right\rfloor\Big) \bmod \max\Big(M\Big(\left\lfloor \dfrac{l+r}{2} \right\rfloor+1, r\Big),7\Big)\right) + \Big(a_{\left\lfloor \frac{l+r}{2} \right\rfloor} - 1\Big) & \text{if } r-l>5,\[1em] \max\limits_{l\leq i\leq r} a_i & \text{if } r-l\leq 5. \end{cases} ]

Note:

• \(\left\lfloor x \right\rfloor\) denotes the largest integer not greater than \(x\). For example, \(\left\lfloor 4.2 \right\rfloor=4\) and \(\left\lfloor 5 \right\rfloor=5\).
• \(\max(a, b)\) returns the larger of \(a\) and \(b\).
• \(\max\limits_{l\le i\le r} a_i\) is the maximum element in the subsequence \(a_l, a_{l+1}, \dots, a_r\).

Your task is: Given \(n\) and the sequence \(a\), compute \(M(1, n)\).

inputFormat

The first line contains a single integer \(n\) (the length of the sequence). The second line contains \(n\) space-separated positive integers representing the sequence \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single integer representing \(M(1, n)\).

sample

7
1 2 3 4 5 6 7

7