Maximum Trees in an Equally Spaced Increasing Subsequence

There are \(n\) trees planted from left to right, where the height of the \(i\)-th tree is \(h_i\). The trees are initially equally spaced. You are allowed to remove some trees so that the remaining trees are equally spaced, and their heights are strictly increasing from left to right. In other words, if the positions of the remaining trees form an arithmetic sequence \(i, i+d, i+2d, \ldots\) (with constant gap \(d\)), then they must satisfy \(h_i < h_{i+d} < h_{i+2d} < \cdots\). Determine the maximum number of trees that can be retained.

inputFormat

The first line contains an integer \(n\) representing the number of trees. The second line contains \(n\) space-separated integers \(h_1, h_2, \ldots, h_n\) representing the heights of the trees.

outputFormat

Output a single integer representing the maximum number of trees that can be retained.

sample

1
5

1