Mauka Mauka

0

0 votes
Problem

The ICC Cricket World Cup 2015 fever is rising up day by day as India is consistently beating every strong team of the world. Fans of the Indian Cricket Team also say that it is not just World Cup, it is the World against India.

The next match of India is semi final with Australia on March 26, 2015. So Australia knowing that Indian Cricket team has the most passionate, aggressive and skilled players has fear of losing in the semi finals and has sent a delegate to negotiate with the Coach of the Indian Cricket team. The Australian delegate tried as hard as he could to convince the Indian Coach but the Indian Coach resisted all the time.

But then suddenly the coach had a thought in his mind that her daughter Tanya was stuck in a programming assignment and had asked the delegate to get the programming assignment of her daughter done. The coach will only rethink about negotiation if the delegate gets the programming assignment of her daughter done.

The programming assignment is as follows: Tanya was given an array 'a' of positive integers of size n by her teacher and asked to find the length of the longest increasing subsequence of the array with the property that no 2 adjacent elements of the subsequence shall be co-prime.

You are a renowned programmer of Australia, whom your delegate friend has asked to solve the programming assignment. Help your delegate friend in completing Tanya's assignment, and making Australia win the semi-finals.

Input

The first line of input consists of a single integer n, denoting the size of the given array. The next line has n positive integers, each separated by a single space, denoting the array elements. For every array index i such that 2 <= i <= n, a[i-1] < a[i] .

Output:

Output the length of the longest strictly increasing subsequence fulfilling the special condition.

Constraint:

1 <= n <= 10^5

1 <= a[i] <= 10^5

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The subsequence is 2, 4, 6 and hence it's length is 3

Editor Image

?