스타크 트레이닝 timer 1s memory 256MB

저글링 유저 진서는 온라인상에서 유명하다. 

저글링 한 마리로 게임을 승리한다. 

테란 유저인 지헌이는 마린 100마리로 싸웠지만 졌다. 

헉!!! 그 이유가 궁금했던 지헌이는 스타크의 전설 영호에게 자문을 구했다.

영호 왈 “흠! 뭉치기 신공이군.. 어쩌구 저쩌구...”

이유는 그랬다. 진서는 저글링을 1000 마리까지 뭉쳐 한 마리처럼 보이게 하는 능력자였던 것이다. 

비밀을 알게 된 지헌이는 그날부터 마린 뭉치기 훈련에 돌입했다. 

어언 1년이 지나 한 마리에 2000마리의 마린을 뭉칠 수 있게 된 지헌이... 승리의 나날이 지속되고 있었다. 

그런데 어느 순간부터 그 비법을 아는 사람이 많아져 새로운 뭉치기 신공을 개발할 필요가 생겼다. 

뭉친 마린이 여러 마리라면 좋을 것 같았다. 그래서 또 다시 수련에 돌입한다.

마린을 세울 섹터를 번호를 정하여 일렬로 만든다. 특정 구간의 각각의 섹터에 1마리씩 추가로 뭉치는 것을 동시에 시행한다.

예를 들어 7개의 섹터를 만들고 아래와 같이 구간 뭉치기를 4번 한다고 하자. 구간 뭉치기를 한 번 할 때마다 해당 구간에 있는 각 섹터에 마린을 1마리씩 추가로 뭉친다.

이렇게 수련하던 지헌이는 갑자기 최종으로 뭉쳐진 마린들을 정렬했을 때의 중앙값이 궁금해졌다. 위의 예에서라면 중앙값은 1이 된다.

지헌이의 수련 기록을 입력받아 뭉쳐진 마린의 중앙값을 계산하는 프로그램을 작성해보자.