The Boneli test P47121


Statement
 

pdf   zip

html

[r]

Apart from the Voight-Kampff test, there is a simpler way to identify repicants: the Boneli test. (It measures the speed of the reflex-arc response which takes place in the upper ganglia of the spinal column. Much simpler, indeed…) Since Rick Deckard is falling in love with Rachael, he will use the Boneli test as an excuse to try to seduce her (it). Cunning Rick has told Rachael that, to apply the test, he must measure the blood pressure near her (its) heart!

Rick already took n measures (and yes, he seduced Rachael), but now he wonders if those measures may have some interest. For every subsequence of c consecutive measures, Rick only takes into account its maximum value. Rick wants to know, among the maximums of all those subsequences (overlapping or not), which is the minimum value m.

For instance, if c = 3, n = 5, and the sequence is 7 4 2 6 8, we have three subsequences: 7 4 2, 4 2 6, and 2 6 8. Therefore, m = 6 for this example, corresponding to the middle subsequence.

Input

Input consists of several cases, each with c and n, followed by n natural numbers. Assume 1 ≤ cn ≤ 106. A case with c = n = 0 ends the input.

Output

For every case, print its corresponding m.

Public test cases
  • Input

    3 5
    7 4 2 6 8
    
    1 1
    500000000
    
    1 2
    1 3
    
    2 2
    1 3
    
    2 5
    0 0 0 0 0
    
    0 0
    

    Output

    6
    500000000
    1
    3
    0
    
  • Information
    Author
    Marçal Garolera
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Sisè Concurs de Programació de la UPC - Semifinal
    Date
    2008-06-28