Jump Game Experience

This is a jump game. In this game, you can jump to any position among n points: \(1, 2, 3, \cdots, n\). Jumping to point \(i\) gives you a reward score \(a_i\). The twist is that for every pair of positions \((x, y)\) with \(1\le x\le y\le n\), a jump from \(x\) to \(y\) grants you an experience value based on the following rule:

$$\operatorname{score}_{x,y}=\begin{cases} \operatorname{len} & \text{if }\gcd(a_x, a_{x+1}, \dots, a_y)=2 \text{ and } \operatorname{len}\bmod 2 = 0\\[8pt] \operatorname{len} & \text{if }\gcd(a_x, a_{x+1}, \dots, a_y)=3 \text{ and } \operatorname{len}\bmod 2 = 1\\[8pt] 0 & \text{otherwise} \end{cases} $$

Here, \(\operatorname{len}\) denotes the length of the segment, i.e. \(y-x+1\). Note: For each pair \((x,y)\), even if you jump multiple times, you only collect the experience value once.

Your task is to write a program that calculates the maximum total experience you can obtain in this game by summing the experience values for all valid pairs \((x,y)\).

inputFormat

The first line contains a positive integer \(n\) representing the number of points.

The second line contains \(n\) space-separated integers, \(a_1, a_2, \dots, a_n\), where each \(a_i\) represents the reward score at point \(i\).

outputFormat

Output a single integer: the maximum total experience obtainable from the game.

sample

3
2 3 6

1