준석이는 정글히트 게임(-도시를 키우고 적을 공격하는 스마트폰 게임)을 아주 좋아합니다. 그는 게임 안에서 일렬로 N개의 건물을 지었습니다. 이 건물들은 각각의 높이가 있습니다.

하지만 건물을 지었다는 기쁨도 잠시, 건물을 짓느라 무리한 준석이는 자금난에 허덕이다가 결국 건물들을 그의 친구인 형준이에게 팔 수밖에 없는 상황에 놓였습니다. 형준이는 준석이의 건물 중 K개 이상으로 이루어진 연속된 구간을 잡아 이를 사려고 합니다.

준석이는 건물을 팔면서, 그 건물들의 (최대 높이) * (최소 높이)만큼의 돈을 받기로 했습니다. 건물의 개수와는 상관없이 말이죠.

준석이는 이 (K개 이상의 연속된)건물들을 팔아 최대한의 돈을 얻고자 합니다. 준석이가 얻을 수 있는 최대한의 돈을 알려 주세요! 건물의 개수는 상관이 없습니다.

Joseph Smith Bang timer 1s memory 128MB

Joseph Smith Bang 1s 128MB