Fly height mode

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You like tracking airplane flights a lot. Specifically, you maintain history of an airplane’s flight at several instants and record them in your notebook. Today, you have recorded N such records h_{1}, h_{2}, ..., h_{N}, denoting the heights of some airplane at several instants. These records mean that airplane was first flying on height h_{1}, then started changing its height to h_{2}, then from h_{2} to h_{3} and so on. The airplanes are usually on cruise control while descending or ascending, so you can assume that plane will smoothly increase/decrease its height from h_{i} to h_{i + 1} with a constant speed. You can see that during this period, the airplane will cover all possible heights in the range [min(h_{i}, h_{i+1}), max(h_{i}, h_{i+1})] (both inclusive). It is easy to see that the plane will be at all possible heights in the range exactly a single instant of time during this ascend/descend.
You are interested in finding the maximum integer K such that the plane was at some height exactly K times during the flight.
Input
There is a single test case.
First line of the input contains an integer N denoting the number of records of heights of the plane.
Second line contains N space separated integers denoting h_{1}, h_{2}, ..., h_{N}.
Output
Output a single maximum integer K in one line, such that the plane was at some height exactly K times during the flight.
Constraints
 h_{i} ≠ h_{i+1}
Subtasks
Subtask #1: (30 points)
 1 ≤ N ≤ 1000
 1 ≤ h_{i} ≤ 1000
Subtask #2: (70 points)
 1 ≤ N ≤ 10^{5}
 1 ≤ h_{i} ≤ 10^{9}
Example
Input: 5 1 2 3 2 3 Output: 3
Explanation
The flight can be draw as:
3 /\/ 2 / 1
There are infinitely many heights at which the plane was 3 times during the flight, for example 2.5, 2.1. Notice that the plane was only 2 times at height 2. Moreover, there are no height at which the plane was more than 3 times, so the answer is 3.
Author:  pkacprzak 
Tags  linesweep ltime43 pkacprzak simple sorting 
Date Added:  28122016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions