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 h1, h2, ..., hN, denoting the heights of some airplane at several instants. These records mean that airplane was first flying on height h1, then started changing its height to h2, then from h2 to h3 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 hi to hi + 1 with a constant speed. You can see that during this period, the airplane will cover all possible heights in the range [min(hi, hi+1), max(hi, hi+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.
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 h1, h2, ..., hN.
Output a single maximum integer K in one line, such that the plane was at some height exactly K times during the flight.
- hi ≠ hi+1
Subtask #1: (30 points)
- 1 ≤ N ≤ 1000
- 1 ≤ hi ≤ 1000
Subtask #2: (70 points)
- 1 ≤ N ≤ 105
- 1 ≤ hi ≤ 109
Input: 5 1 2 3 2 3 Output: 3
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.
|Tags||line-sweep, ltime43, pkacprzak, simple, sorting|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.