Minimum Number of Robot Families

In the future era of artificial intelligence, robots have taken over factories. On a factory conveyor belt, there are N robots arranged sequentially, and the mass of the i-th robot is given by \(A_i\). After careful observation, two key properties are noted:

1. All robots from the same family appear consecutively in the list of \(N\) robots.
2. If the robots from index \(i\) to \(j\) (inclusive) belong to the same family, then after sorting these robots by mass in increasing order, the sorted sequence forms a subsequence of an arithmetic progression with a common difference greater than \(1\). In other words, if the sorted masses are \(s_1, s_2, \dots, s_k\) (with \(k \ge 2\)), then there exists an integer \(d > 1\) such that for each \(t\) (\(2 \le t \le k\)), \(s_t - s_1\) is a multiple of \(d\). Note that a single-element family is always valid.

OpenAI has discovered that the fewer the different families, the more united the robots are, increasing their likelihood of escaping the factory. Given the masses of the N robots, determine the minimum number of different families they can belong to while satisfying the above conditions.

inputFormat

The first line contains an integer \(N\) (\(1 \le N \le 10^5\) or moderate constraints as per the problem), the number of robots.

The second line contains \(N\) space-separated integers \(A_1, A_2, \dots, A_N\) representing the masses of the robots.

outputFormat

Output a single integer representing the minimum number of families into which the robots can be partitioned.

sample

5
7 3 5 10 2

2