Longest Prime Increasing Subsequence

You are given a sequence of integers. Your task is to compute the length of the longest strictly increasing subsequence composed solely of prime numbers extracted from the given sequence.

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. If the sequence does not contain any prime numbers, the answer should be 0.

The subsequence is not required to be contiguous, but the order of elements must remain the same as in the original sequence.

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 10^5), which indicates the number of integers in the sequence. The second line contains n space-separated integers.

outputFormat

Output a single integer: the length of the longest strictly increasing subsequence of prime numbers extracted from the sequence. If no prime number exists, output 0.## sample

8
7 2 5 3 11 13 1 17

5