중앙값 산맥

베르란드는 지형이 다양한 큰 나라이다. 이 나라에서 가장 유명한 자연 명소 가운데 하나가 '중앙값 산맥'이다. 이 산맥은 한 직선 위에 놓인 $n$개의 산봉우리로 이루어져 있으며, 왼쪽부터 1번에서 $n$번까지 차례로 번호가 붙어 있다. $i$번째 산봉우리의 높이는 $a_i$이다.

이 산맥에서는 매일 산봉우리 정렬이 일어난다. 정렬 순간에 2번부터 $n-1$번까지 모든 산봉우리의 높이가 동시에 바뀐다. 정렬 전 높이가 $b_i$라고 하면, 새 높이 $a_i$는 다음과 같다. $a_1 = b_1$, $a_n = b_n$이고, 2 이상 $n-1$ 이하의 모든 $i$에 대해 $a_i$는 median$(b_{i-1}, b_i, b_{i+1})$이다. 세 정수의 중앙값은 그 가운데 두 번째로 큰 수이다. 예를 들어 median$(5,1,2) = 2$이고 median$(4,2,4) = 4$이다.

베르란드 과학자들은 초기 높이가 어떤 값이든 정렬 과정이 조만간 안정된다는 것을 증명했다. 즉 어느 시점부터는 정렬을 해도 높이가 더 이상 바뀌지 않는다. 정부는 이 과정이 얼마나 빨리 끝나는지 알고 싶어 한다. 높이를 하나 이상 바꾸는 정렬이 몇 번 일어나는지, 곧 $c$의 값을 구하라.

일부 테스트 그룹에서는 $c$와 함께 $c$번의 정렬을 마친 뒤 산봉우리의 높이, 즉 이후 영원히 유지되는 높이도 구해야 한다.

첫째 줄에 정수 $n$과 $t$ ($1 \le n \le 500\,000$, $0 \le t \le 1$)가 주어진다. $n$은 산봉우리의 개수이고, $t$는 최종 높이를 출력해야 하는지를 나타낸다.

둘째 줄에 정수 $a_1, a_2, a_3, \ldots, a_n$ ($1 \le a_i \le 10^9$)이 주어진다. 이는 산봉우리의 현재 높이이다.

첫째 줄에 높이를 하나 이상 바꾸는 정렬의 횟수 $c$를 출력한다.

$t = 1$이면 둘째 줄에 $c$번의 정렬을 마친 뒤 $n$개 산봉우리의 최종 높이를 출력한다.

첫 번째 예시에서 1번과 5번 산봉우리의 높이는 전혀 바뀌지 않는다. median$(1, 2, 1) = 1$이므로 첫 정렬 후 2번과 4번 산봉우리의 높이는 모두 1이 된다. median$(2, 1, 2) = 2$이므로 3번 산봉우리의 높이는 2가 된다. 따라서 첫 정렬 후 높이는 1, 1, 2, 1, 1이다. 두 번째 정렬 후에는 모두 1이 되고, 이후로는 변하지 않는다. 그러므로 높이를 바꾸는 정렬은 2번뿐이다.

세 번째 예시에서는 정렬을 해도 어떤 높이도 바뀌지 않으므로 횟수는 0이다. $t = 0$이므로 최종 높이는 출력하지 않는다.