Background

在动态规划专题的学习中，刘学习学习了如何求解最长不降子序列。
毕业后他去面试，面试官又问了他这个问题，但是这次似乎有点不对劲……

Description

面试官说，一个不降子序列中相邻的数相差太大很不好，不要超过K(K>=0)。
刘学习并不会做，冷汗直冒。他只好码了裸的最长不降子序列并输出。
但是他竟然蒙对了，通过面试进入了公司。
多年以后，已经走上人生巅峰的他回想起这次面试，仍然觉得相当奇怪。
他找来了当时的输入序列，但是他忘了K的值。
于是他想知道，这个拯救了他的K至少有多大。

Format

Input

包含不多于5组输入数据，请处理到文件结束。
每组数据第一行包含一个整数n(n<=100000)。
第二行包含n个10^9内的正整数，表示输入序列。

Output

按照输入顺序，对于每组输入数据，输出一行一个整数表示答案。

Sample 1

Input

5
1 3 2 5 4

Output

2

Limitation

10s, 512MB for each test case.

Source

Vijos Original