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.
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.
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:
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:
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 ti.
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.
6 6 2 4 5 1 3
5 1 3 5 4 2
The first sample case is the example given earlier:
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.
The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.