oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

peaks Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

peaks.html

Problem Description

Rar the cat has been observing mountains and has recorded the heights of a particular mountain range at every specific interval and recorded them into a list, forming a landscape. Now, he wants to process these data in order to make a better interpretation of the landscape. To do so, Rar the cat has decided to identify peaks. Rar the cat consider a place as a 1st-degree peak if the heights of the surroundings are strictly lower than itself. (Eg. 2 7 3, 7 will be the peak).

However this is not enough! A 1st-degree peak can be 'upgraded' to a 2nd-degree peak if the 2 adjacent 1st-degree peaks are lower than it. For example: If the heights recorded of the landscape are 2 5 3 7 4 1 6 2, then the 1st-degree peaks would be 5, 7 and 6. Since the 2 adjacent 1st-degree peaks of 7 is lower than itself, 7 is considered a 2nd-degree peak but 5 and 6 are still 1st-degree peaks.

Extending this rule, a X-degree peak can be 'upgraded' to a X+1-degree peak if the 2 adjacent X-degree peaks are lower than it.

Given the landscape, Rar the cat wants to know the degree of the highest degree peak.

Input

A single integer, N. N denotes the number of positive integral heights that Rar the cat has recorded.

The following line consists of N integers, with each being in the range of 1 to 1000000000.

Output

Output a single integer, the degree of the highest degree peak. If there are no 1st-degree peaks at all, then output 0 instead.

Limits

Subtask 1 (35%): 0 < N ≤ 5000

Subtask 2 (65%): 0 < N ≤ 3000000

Subtask 3 (0%): As per sample testcases.

Sample Testcase 1

Input:

8
2 5 3 7 4 1 6 2

Output:

2

Sample Testcase 2

Input:

8
1 2 3 4 5 6 7 8

Output:

0

Tags

Raffles Cat Helping Practice Contest 2013, Ad Hoc

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
13553s64MBMinimum
26553s64MBMinimum
3023s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o peaks -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.