Bob is kicking back and relaxing today! He plans to continually watch TV for
Constraints
For all subtasks:
Subtask 1 [20%]
Subtask 2 [80%]
Input Specification
The first line will contain one integer representing
The second line will contain
The third line will contain
Output Specification
Output
Maximizing the minimum - consider the minimum of ratings of the TV shows Bob watches. This minimum changes depending on at what times Bob switches the channel. To maximize the minimum is to find the largest such value over all possible ways Bob can switch channels in
Sample Input 1
6
10 21 15 13 17 15
18 20 18 22 14 19
Sample Output 1
10
14
15
17
17
17
17
Explanation for Sample 1
For zero switches, Bob can only sit back and watch the entire first channel. With one switch, Bob can change the channel right before the first show and watch the entire second channel. For two switches, Bob changes the channel before the first and fifth shows. For three switches, Bob also changes the channel before the sixth show. Even with more switches, Bob cannot get any better value than
Sample Input 2
5
1 2 1 2 1
2 1 2 1 2
Sample Output 2
1
1
1
1
1
2
Comments
Maximizing the minimum - consider the minimum of ratings of the TV shows Bob watches. This minimum changes depending on at what times Bob switches the channel. To maximize the minimum is to find the largest such value over all possible ways Bob can switch channels in
switches or less.