题目描述

小蓝从左到右种了 $n$ 棵小树，第 $i$ 棵树的高度为 $h_i$，相邻树的间隔相同。小蓝想挪走一些树使得剩下的树等间隔分布，且从左到右高度逐渐上升（相邻两棵树高度满足右边的比左边的高），小蓝想知道最多能留下多少棵树。

输入格式

输入的第一行包含一个正整数 $n$。

第二行包含 $n$ 个正整数 $h_1, h_2, \cdots, h_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例

6
3 5 4 7 6 7

3

解释 #1

留下第 1、3、5 棵树，它们等间隔且从左到右高度逐渐上升。

数据范围

• 对于 $30\%$ 的评测用例，$1 \leq n \leq 500$；
• 对于 $60\%$ 的评测用例，$1 \leq n \leq 3000$；
• 对于所有评测用例，$1 \leq n \leq 5000$，$0 < h_i < 10^6$。