[Solution] Beautiful Array Codechef Solution

Problem

You're given an array $A$ of $N$ integers. You need to find the minimum cost of creating another array $B$ of $N$ integers with the following properties

• $B_i \ge 0$ for each $1 \leq i \leq N$
• The GCD of adjacent elements of $B$ is equal to $1$, i.e, $\gcd(B_i, B_{i+1}) = 1$ for each $1 \leq i \lt N$

The cost of creating $B$ is defined as follows:

$$\sum_{i=1}^{N} 2^{|A_i - B_i |}$$

Find the minimum possible cost to create the array $B$. Since the answer can be huge print it modulo $10^9+7$

Note: You need to minimize the value of total cost of creating the array $B$, and then print this minimum value modulo $10^9 + 7$. For example, suppose there is a way to create the required $B$ with a cost of $500$, and another way to do it with a cost of $10^9 + 7$ (which is $0 \pmod {10^9 + 7}$). The output in this case would be $500$ and not $0$.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• The first line of each test case contains an integer $N$ - the length of the array $A$
• The second line of each test case contains $N$ space-separated integers $A_1,A_2,\ldots,A_N$

Output Format

For each test case, output on a new line the minimum cost of creating the array $B$, modulo $10^9 + 7$.