Informatica Online Judge

  Bad Hair Day의 강강술래 [1955 / 07A3]

Time Limit(Test case) : 500(ms)
Number of users who solved : 12   Total Tried : 13


The Champion of this Problem (C++) : gs16106 - 0ms / 855byte
My Best Submission (C++) : N/A

[koistudy.net (T. JKJeong 2017)]

Background

koistudy에서 유명한 USACO의 Silver문제 Badhair day를 알고 있을 것이다.

잘 모르면 200번 문제를 참고하도록 하자.

[BadHair Day 문제보기]

이번에는 키가 각각 $h_1,~h_2,~...h_n$인 $n$마리의 소들이 한 줄로 서 있는 것이 아니라 강강술래를 하기위하여 환형(원형)으로 서 있다.

따라서 누가 시작인지 끝인지를 구분할 수 없다.

예를 들어서 소들이 다음과 같이 서 있다고 가정해보자.



이 그림에서 2와 10사이의 선을 끊어서 시계방향으로 나열하면 다음과 같은 순서가 된다.

10 3 7 4 12 2

이 때의 Bad Hair Day문제 답을 구하면 5가 된다.

하지만 4와 12사이를 끊어서 나열하면 다음과 같은 순서가 된다.

12 2 10 3 7 4

이 때의 답은 9가 된다.

어떤 방법으로 끊어서 소들을 나열하느냐에 따라서 답이 달라진다.

이 문제의 목적은 나열하여 얻을 수 있는 최댓값과 최솟값을 구하는 것이다.

주어진 입력에 대해서 가능한 최댓값과 최솟값을 구하는 프로그램을 작성하시오.

Input

$n$

${h_1}~~{h_2}~~...~~{h_n}$

[입력값의 정의역]
$3 ≤ n ≤ 80,000$
각 소들의 키는 $10^9$을 초과하지 않는 자연수

Output

가능한 나열에서 구한 최댓값과 최솟값을 공백으로 구분하여 출력한다.

IO Example

입력
6
10 3 7 4 12 2

출력
9 3


* 설명 :
12 2 10 3 7 4 로 나열 했을 때가 9로 최대이고
3 7 4 12 2 10 으로 나열 했을 때는 3으로 최소이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]