For a non-continuous subsequence S of length K, the beauty is calculated as follows:

Question

You are given an array A of size N.

For a non-continuous subsequence S of length K, the beauty is calculated as

follows:

If the length of the subsequence is 1 then the beauty is 0. pretty2020

If the length of the subsequence is greater than 1 then the beauty is the sum of

(S[i + 1] - S[i]) ^ 2 for all 1 <= i < k

Find the maximum possible beauty of a subsequence such that the GCD of the

absolute values of S is greater than 1. Since the answer can be large, return it

modulo 10 ^ 9 + 7

Input Format

The first line contains an integer, N, denoting the number of elements in A.

Each line i of the N subsequent lines (where 0 <= i < N ) contains an integer

describing A[i].

Constraints

1 <= N <= 10 ^ 5

N <= A[i] <= N

Sample Test Cases

Case 1

Input:

5

1

2

1

2

1

Output:

1

Explanation:

Given N=5, A= [1, 2, 1, 2, 1]

We can choose a subsequence as [1, 2], which consists of only two elements and

satisfies the necessary conditions.

Hence, the beauty of this subsequence is equal to 0.

Case 2

Input:

5

5

3

4

2

1

Output:

4

Explanation:

Given N=5, A= [5, 3, 4, 2, 1]

We can choose a subsequence which consists of elements [4, 2].

The beauty of this subsequence is (4-2)^2 which is equal to 4.

Case 3

Input:

6

1

6

2

5

4

3

Output:

81

Explanation:

Given N= 6, A = [1, 6, 2, 5, 4, -3]

We can choose a subsequence which consists of elements [6, -3].

The beauty of this subsequence is (6 - (- 3)) ^ 2 which is equal to 81

Answer 1

def max_beauty_subsequence(N, A):
 MOD = 10**9 + 7
 
 # Function to calculate GCD
 def gcd(x, y):
 while y:
 x, y = y, x % y
 return x
 
 max_beauty = 0
 
 # Check each possible subsequence
 for i in range(N):
 for j in range(i + 1, N):
 subseq = A[i:j+1]
 subseq_len = len(subseq)
 
 # Check GCD condition
 if subseq_len > 1:
 current_gcd = abs(subseq[0])
 for num in subseq[1:]:
 current_gcd = gcd(current_gcd, abs(num))
 if current_gcd > 1:
 break
 
 if current_gcd > 1:
beauty = sum((subseq[k] - subseq[k-1])**2
for k in range(1, subseq_len))
 max_beauty = max(max_beauty, beauty % MO
D)
 
 return max_beauty
# Example usage:
N = 5
A = [1, 2, 1, 2, 1]
print(max_beauty_subsequence(N, A)) # Output: 1