34929번 - 중앙값의 함정 스페셜 저지

문제

칠판에 $N$개의 정수가 적혀 있다. 한별이는 아래와 같은 시행을 반복해 칠판에 정수가 하나만 남게 하려 한다.

• 칠판에 적힌 세 수를 골라 지우고 세 수의 중앙값을 쓴다.

한별이는 칠판에 마지막에 남은 수가 최대가 되게 하려고 한다. 한별이를 도와 마지막에 남은 수의 최댓값과 그 시행 방법을 구해보자.

입력

첫째 줄에 칠판에 적힌 정수의 개수 $N$이 주어진다. $(1\le N\le 299,円 999;$ $N$은 홀수$)$

둘째 줄에 칠판에 적힌 $N$개의 정수 $a_1,a_2,\cdots ,a_N$이 공백으로 구분되어 주어진다. $(-10^{9}\le a_i\le 10^{9})$

출력

첫째 줄에 칠판에 마지막으로 남은 정수의 최댓값을 출력한다.

둘째 줄부터 $\displaystyle{\frac{N-1}{2}}$개 줄에 걸쳐 마지막으로 남은 정수가 최대가 되도록 하는 시행을 한 줄에 하나씩 순서대로 출력한다. 각 시행은 시행에서 고른 세 수를 순서에 관계없이 공백으로 구분해 출력한다. 그런 방법이 여러 개라면 그중 아무거나 출력한다.

제한

노트

세 수의 중앙값은 세 수 중 두 번째로 큰 수를 의미한다. 예를 들어 5ドル,ドル 2ドル,ドル 4ドル$의 중앙값은 4ドル$이고, 3ドル,ドル 3ドル,ドル 2ドル$의 중앙값은 3ドル$이다.