히스토그램에서 가장 큰 직사각형과 쿼리 2
시간 제한2초메모리 제한1024 MB
막대 N개의 높이가 주어질 때, l번째부터 r번째까지의 막대만 남겼을 때 만들 수 있는 가장 큰 직사각형의 넓이를 구합니다.
문제
Study nature: 자연을 탐구하고 세상의 문제를 발견하는 인재.
위 문장은 KSA 비전 2040에서 공개된 모토의 일부다.
하지만 본 문제의 출제자는 KSA를 졸업했으므로, 남의 문제를 베껴오기로 하였다. 본 문제는 '히스토그램에서 가장 큰 직사각형과 쿼리' 문제를 몇 글자만 바꾼 것이다.
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 너비가 로 일정하지만, 높이는 서로 다를 수도 있다. 예를 들어, 다음 그림은 높이가 인 직사각형으로 이루어진 히스토그램이다.
이 히스토그램에서 아래와 같은 쿼리 개를 수행해보자.
- : 번째 직사각형부터 번째 직사각형까지만 있을 때, 가장 넓이가 큰 직사각형의 넓이를 출력한다.
입력
첫 번째 줄에 직사각형의 수 이 주어진다.
두 번째 줄에는 히스토그램에서 각 직사각형의 높이를 나타내는 개의 정수 가 공백으로 구분되어 왼쪽에서 오른쪽으로 순서대로 주어진다.
세 번째 줄에는 쿼리의 수 가 주어진다.
다음 개의 줄에 쿼리들의 정보가 주어지며, 각 줄에는 두 개의 정수 , 이 공백으로 구분되어 주어진다.
출력
개의 줄에 걸쳐 각 쿼리의 정답을 출력한다.