프로그램 명: rectangle

제한시간: 1 초

히스토그램은 통계치를 연속적인 사각형 형태로 나타내어 보기 좋게 만든 다각형이다. 모든 사각형의 폭은 동일하고 높이는 다르다.

아래 그림은 폭 1 을 가지고 높이가 각각 2, 1, 4, 5, 1, 3, 3 인 히스토 그램이다.

보통 , 텍스트에 있는 문자의 빈도수를 구하는 것 처럼 이산 분포에서 흔히 사용된다.

문제는 히스토그램에서 밑 하단의 기저 라인과 평행한 가장 큰 직사각형의 넓이를 계산하는 것이다. 그림에서 왼쪽 히스토 그램에서 오른쪽 그림의 빗금 친 부분이 가장 큰 넓이를 가지는 직사각형이다.

입력의 첫 수는 사각형의 개수 n 이고 다음 n 개의 정수는 높이 h1 , h2 , ... ,hn 을 나타낸다. 1<=n<=100000 , 0<=hi<=1000000000 이다.

최대 넓이를 출력한다.

입력

7 2 1 4 5 1 3 3

출력

8

입력

4 1000 1000 1000 1000

출력

4000

-큰 데이터 입력되므로 cin 보다는 scanf 로

32 비트 정수 범위를 초과하므로 64 비트 정수를 사용

long long a;

printf("%lld",a);

출처: Ulm Local 2003