중앙줄기

n 개의 정수 배열 arr이 제공됩니다. 각 인덱스 i (0과 n-1 포함)에 대해 output[i]가 arr[0 .. i] 요소의 중앙값(median)이 되도록 output 배열을 계산합니다.

정수 배열의 중앙값(median)은 다음과 같이 정의됩니다.

• 홀수의 정수가 있는 경우, 중앙값은 정렬된 순서에서 중간 정수와 같습니다.
• 그렇지 않으면 짝수의 정수가 있으면, 중앙값은 정렬된 순서에서 가장 중간에 있는 두 정수의 평균과 같습니다.
• 평균값이 정수가 아닐 경우 가장 가까운 정수로 내립니다 (Floor).

예제 1

입력

arr = [5, 15, 1, 3]  

출력

[5, 10, 5, 4]
// [5]의 중앙값은 5, 
// [5, 15]의 중앙값은 (5 + 15) / 2 = 10, 
// [5, 15, 1]의 중앙값은 5, 
// [5, 15, 1, 3]의 중앙값은 (3 + 5) / 2 = 4입니다.

예제 2

입력

arr = [1, 2]  

출력

[1, 1]
// [1]의 중앙값은 1이고 
// [1, 2]의 중앙값은 (1 + 2) / 2 = 1.5 
// (1로 내림해야 함)입니다.