히스토그램

히스토그램은 일정한 너비의 막대를 나란히 세운 그래프이다. 각 막대의 높이는 정수로 주어진다. 아래 그림에서는 왼쪽부터 높이가 2, 1, 4, 5, 1, 3, 3이다.

히스토그램 안에 만들 수 있는 직사각형 중 넓이가 가장 큰 것을 찾으려고 한다. 직사각형의 밑변은 항상 히스토그램의 아랫변과 평행해야 하며, 직사각형 전체가 막대들이 차지하는 영역 안에 있어야 한다. 아래 그림의 빗금 친 영역은 가능한 직사각형 중 하나이다.

주어진 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이를 구하라.

첫째 줄에 히스토그램의 가로 칸 수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개 줄에는 각 칸의 높이가 왼쪽부터 차례대로 주어진다. 각 높이는 0 이상 1,000,000,000 이하의 정수이다.

첫째 줄에 히스토그램 안에서 만들 수 있는 가장 큰 직사각형의 넓이를 출력한다. 출력값은 2,000,000,000을 넘지 않는다.