1214: 投球游戏

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:32 Solved:15

Description

有一种投球游戏,玩法时将球投到 $n$ 个篮框里。具体玩法如下:

投篮顺序必须符合以下三个规则:
  • 第一次投篮可以投任意一个篮筐;

  • 从第二次投篮开始,每一次投篮只能投顺序在上一次篮筐后面的篮筐;

  • 从第二次投篮开始,每一次投篮只能投比上一次投篮距离更近的篮筐。

给出 $n$ 个篮筐的距离和顺序,假定每次投篮必进,请你计算按照规则最多能进几个球?

Input

共两行。

第一行,包含一个正整数 $n$,表示篮筐的个数。

第二行,包含 $n$ 个正整数,中间以空格隔开,表示先后顺序固定的篮筐的距离。

数据保证每个篮筐的距离各不相同。

Output

一个整数,表示最多能进的球的数量。

Sample Input Copy

3
130 200 55

Sample Output Copy

2

HINT

数据范围:

$3\le n \le 20$,$10 \lt任一篮筐距离 \lt 1000$。

Source/Category