PEG Judge - Mock CCC14S2

2014 Mock CCC by Alex and Timothy

Problem S2: Sleep Cycle

Alice's obsession with her friend Bob is so tenacious that she cannot fall asleep at night. She decided to come up with a plan to secretly visit Bob in his house while he is sleeping. To not get caught, she must go only when she knows that Bob will be sound asleep for a while. Alice knows that people have sleep cycles. Below is an example of a hynogram, demonstrating the human sleep cycle.

However, every individual's sleep pattern is different and can be affected by many different factors. For instance, Bob's sleep cycle can be different due to his habit of staying up late to watch movies, or due to him being a heavier sleeper than most. The only thing Alice can truly rely on is the cold, hard data she has collected from a high-quality microphone, previously planted outside of Bob's window to monitor his sleeping patterns.

Given N (3 ≤ N ≤ 1000) measurements of Bob's awakeness level recorded at fixed time intervals, Alice would like to know the length of the longest dip in the data. A dip is a consecutive sequence of length three or more that starts at a value, progresses to the minimum value of the sequence in a strictly decreasing pattern, remains at the minimum value for one or more iterations, and progresses back up in a strictly increasing pattern. More specifically, a consecutive subsequence from i to j of a sequence of numbers is a dip if and only if x_i > x_i+1 > … > x_k (= x_k+1 = x_k+2 = …) < … < x_j-1 < x_j. For example, the sequence {7, 5, 4, 2, 1, 2, 8, 10} is a dip of length 8, the sequence {3, 2, 2, 3} is a dip of length 4, but the sequences {1, 1, 1}, {5, 4, 4, 2, 3, 5} and {5, 2, 1, 9, 8, 10} are not dips. Knowing the length of the longest dip, Alice will then be able to determine whether she has an opportunity to break in and watch Bob sleep.

Input Format

Line 1 contains the positive integer N, the number of data points to follow.
Line 2 contains N positive integers each no greater than 1 billion, the measurements of Bob's awakeness levels that Alice has recorded.