Maximum Valid Segments Partitioning

You are given n playing cards, where the i-th card has a positive integer a_i.

You need to partition the cards into several contiguous segments such that each segment [l, r] is valid if and only if it satisfies both of the following conditions:

• a_l < a_r
• \(\gcd(a_l,a_r)>1\) (i.e. the greatest common divisor of a_l and a_r is greater than 1, where the \(\gcd\) function is defined in the hint section if you are not familiar with it)

Your task is to determine the maximum number of segments into which the cards can be partitioned. The partition must cover the entire sequence of cards. If it is impossible to partition the cards into valid segments, output -1.

Note: Each segment must contain at least two cards since the conditions are defined on the first and last card of the segment.

inputFormat

The first line contains an integer n (the number of cards).

The second line contains n positive integers a₁, a₂, ..., a_n separated by spaces.

outputFormat

Output a single integer representing the maximum number of valid segments into which the cards can be partitioned. If no valid segmentation exists, output -1.

sample

5
2 3 4 6 8

2