|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||64 MB||28||12||9||37.500%|
Young Mirka is an amateur musician. She plays the multi-piano. A multi-piano consists of an infinite number of multi-keys, denoted with integers that can be interpreted as the pitch. A multi-composition (a composition written for a multi-piano) can be represented with a finite array of integers, where integers denote the order of multi-keys to press in order to play the multi-composition.
Young Mirka has heard a multi-composition on the multi-radio and now she wants to play it. Unfortunately, she cannot hear exactly which key was pressed, but instead she can hear whether the pressed multi-key was higher, lower or equal to the previously played key (a higher key is denoted with a larger number). Therefore she has decided to play the composition in the following way:
Notice that, when Mirka is playing, she does not compare the pitch of the keys she played to the pitch of the keys from the composition.
Help Mirka choose the integer K in order to hit as many correct pitches as possible.
The first line of input contains the integer N (2 ≤ N ≤ 106), the number of multi-keys in the multicomposition on the multi-radio.
The second line of input contains N integers ai (−109 ≤ ai ≤ 109), the multi-keys played in the multi-composition.
The first line of output must contain the maximum number of multi-keys that Mirka can play correctly. The second line of output must contain the non-negative number K that Mirka must choose in order to hit as many correct pitches as possible. The number must be smaller than or equal to 2 · 109.
Please note: The required number does not have to be unique, but will surely exist within the given constraints.
5 1 2 0 3 1
7 2 1 -6 -2 1 6 10
Clarification of the first example: Mirka will play the following keys, respectively: 1, 2, 0, 3, 1. Denoted in bold are the keys that she played correctly.
Clarification of the second example: Mirka will play the following keys, respectively: 2, -2, -6, -2, 2, 6, 10.