Problem: Slicing Paradise

Want to try solving this problem? You can submit your code online if you log in or register.

Slicing Paradise

Input File: slicein.txt
Output File: sliceout.txt
Time Limit: 1 second

The Piranha Coast is world-famous for its gorgeous old-world forests and its pristine natural beauty. In fact, it's so world-famous, that tourism is booming, with a shiny new resort being built every week ... right on top of the very forests the tourists come to see! In fact, when all the proposed resorts are built, there won't be a tree left.

As Minister for Sarcasm and Snark, you were quick to point out the problems with this. The good news: the old Minister for Tourism and Planning has been sacked. The bad news: now you have the job, and it's too late to stop the resorts from being built. All you can do now is put a positive spin on things.


6	2	4	5	1	3

The Piranha Coast has been divided into N blocks of forestland, each scheduled to be turned into a resort at a different time. In the above diagram, there are six blocks of land, each labelled with a number indicating in what order they are to be turned into resorts. So the block labelled `1' will be turned into a resort first, followed by the block labelled `2' and so on.

To attract tourists, you call the stretches of untouched forestland national parks. (Tourists love national parks.) Your lawyers have given the following definition: a national park is a series of consecutive blocks of forestland bordered on both sides by either resorts or the edge of the Coast.

As more resorts are built, the number of national parks may go up and down. You decide to wait until there are as many national parks as possible, and then use that to launch a splashy advertising campaign: "Come visit the Piranha Coast! Now with P national parks to explore!"

Your task is to write a program that takes a description of the order in which resorts are built, and outputs P, the maximum number of national parks at any time.

Constraints

To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:

1 ≤ N ≤ 100,000, where N is the number of blocks of forestland.
1 ≤ t_i ≤ N, where t_i denotes the time at which the ith block of forestland is turned into a resort. No two blocks of land will be turned into a resort at the same time.

As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large - in particular:

For 30% of the available marks, 1 ≤ N ≤ 1,000.

Input

Your program should read from the file . The first line of this file will contain the integer N. The following N lines will describe the times at which the various blocks of land are turned into resorts: the ith of these lines will contain the integer t_i.

Output

Your program should write to the file . Your output file should consist of a single integer: the maximum number of national parks at any time.

Sample Input 1

Sample Input 2

Sample Output 1

Sample Output 2

Explanation

The first sample case is the example given earlier:

After the first resort is built, the coast is divided into two national parks - one of size 4, and one of size 1.
After the second resort is built, the resort is now divided into three national parks, of sizes 1, 2 and 1. This is the largest number of resorts that will ever be seen.
After the third resort is built, the right-most national park is lost, leaving two national parks of size 1 and 2.
As the remaining resorts are built, we never see any more than three national parks, and therefore the final answer is 3.

In the second sample case, there is never more than one national park present at a time, as resorts are built from the outside, working inwards.

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.