# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Tejas Pandey

Tester: Satyam, Tejas Pandey

Editorialist: Pratiyush Mishra

# DIFFICULTY:

2828

# PREREQUISITES:

None

# PROBLEM:

Chef considers an array *good* if it has no subarray of size less than N such that the GCD of all the elements of the subarray is **equal** to 1.

Chef has an array A of size N with him. He wants to convert it into a *good* array by applying a specific operation.

In one operation, Chef can choose any subarray and **reverse** it.

Find the **minimum** number of operations required to convert the array into a *good* array and the operations themselves. If there are multiple ways to achieve the result, print any.

If it is not possible to convert the array into a *good* array, print -1 instead.

Note: A subarray of an array is formed by deletion of several (possibly zero) elements from the beginning and several (possibly zero) elements from the end of the array.

# EXPLANATION:

Observation \;1: Suppose the gcd(A_1,A_2....A_{n-1}) \neq 1 and gcd(A_2,A_2....A_{n}) \neq 1 , then our array would be good.

This is because if gcd of an array is greater than 1, then any subarray of it would have gcd greater than 1.

First thing we would do is precompute the suffix gcd and prefix gcd, such that

Now we would loop through the array and at any element, say A_i, we would check if

If it satisfies we would either reverse the array A[1,2....i] or array A[i+1,i+2....n] with aim to satisfy the initial condition given in Observation \;1.

Now we can do this in atmost two operations. Initially we would check if prefix[n-1] \neq 1 or suffix[2] \neq 1. If both of these satisfies then no further operation is needed otherwise if any one of them satisfies then we would need one more operation otherwise if none satisfies we would need to do two operations.

# TIME COMPLEXITY:

O(N), for each test case.