문제
Study nature: 자연을 탐구하고 세상의 문제를 발견하는 인재.
위 문장은 KSA 비전 2040에서 공개된 모토의 일부다.
하지만 본 문제의 출제자는 KSA를 졸업했으므로, 남의 문제를 베껴오기로 하였다. 본 문제는 히스토그램에서 가장 큰 직사각형과 쿼리 (16977)를 베껴와 몇 글자만 바꾼 문제다.
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 너비가 1ドル$로 일정하지만, 높이는 서로 다를 수도 있다. 예를 들어, 다음 그림은 높이가 3,ドル 5, 8, 8, 4, 7$인 직사각형으로 이루어진 히스토그램이다.
히스토그램에서 아래와 같은 쿼리 $Q$개를 수행해보자.
- $l ,円 r$: $l$번째 직사각형부터 $r$번째 직사각형까지만 있을 때, 가장 넓이가 큰 직사각형의 넓이를 출력한다.
출력
$Q$개의 줄에 걸쳐 각 쿼리의 정답을 출력한다.
제한
- 1ドル\leq N,Q\leq 10^5$
- 1ドル\leq H_i\leq 10^9$
- 1ドル\leq l\leq r\leq N$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 4 | $Q \leq 300$
|
| 2 | 40 | $H_1 < H_2 < \cdots < H_N$
|
| 3 | 32 | $i\neq j \Rightarrow H_i \neq H_j$
|
| 4 | 24 | 추가 제약 조건 없음
|
예제 출력 1
20
10
16
16
12
W3sicHJvYmxlbV9pZCI6IjMxNDQwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVhY2ZjIFx1Y2ZmY1x1YjlhYyAyIiwiZGVzY3JpcHRpb24iOiI8YmxvY2txdW90ZT5cclxuPHA+U3R1ZHkgbmF0dXJlOiBcdWM3OTBcdWM1ZjBcdWM3NDQgXHVkMGQwXHVhZDZjXHVkNTU4XHVhY2UwIFx1YzEzOFx1YzBjMVx1Yzc1OCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViYzFjXHVhY2FjXHVkNTU4XHViMjk0IFx1Yzc3OFx1YzdhYy48XC9wPlxyXG48XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+XHVjNzA0IFx1YmIzOFx1YzdhNVx1Yzc0MCBLU0EgXHViZTQ0XHVjODA0IDIwNDBcdWM1ZDBcdWMxMWMgXHVhY2Y1XHVhYzFjXHViNDFjIFx1YmFhOFx1ZDFhMFx1Yzc1OCBcdWM3N2NcdWJkODBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWJjZjggXHViYjM4XHVjODFjXHVjNzU4IFx1Y2Q5Y1x1YzgxY1x1Yzc5MFx1YjI5NCBLU0FcdWI5N2MgXHVjODc4XHVjNWM1XHVkNTg4XHVjNzNjXHViYmMwXHViODVjLCBcdWIwYThcdWM3NTggXHViYjM4XHVjODFjXHViOTdjIFx1YmNhMFx1YWVmNFx1YzYyNFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YmNmOCBcdWJiMzhcdWM4MWNcdWIyOTQgPGEgaHJlZj1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3Byb2JsZW1cLzE2OTc3XCI+XHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVhY2ZjIFx1Y2ZmY1x1YjlhYyAoMTY5NzcpPFwvYT5cdWI5N2MgXHViY2EwXHVhZWY0XHVjNjQwIFx1YmE4NyBcdWFlMDBcdWM3OTBcdWI5Y2MgXHViYzE0XHVhZmJjIFx1YmIzOFx1YzgxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzQwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVhYzAwIFx1YzU0NFx1Yjc5OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YjNjNFx1ZDYxNVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWIxMDhcdWJlNDRcdWFjMDAgJDEkXHViODVjIFx1Yzc3Y1x1YzgxNVx1ZDU1OFx1YzljMFx1YjljYywgXHViMTkyXHVjNzc0XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5N2MgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViMmU0XHVjNzRjIFx1YWRmOFx1YjliY1x1Yzc0MCBcdWIxOTJcdWM3NzRcdWFjMDAgJDMsIDUsIDgsIDgsIDQsIDckXHVjNzc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91LmFjbWljcGMubmV0XC9lZjljYzA2MC01MTg2LTRkZmItYTgxNC1lMjI2NmZiMTZlMmVcL2hpc3RvXzEud2VicFwiIHN0eWxlPVwid2lkdGg6IDM1OXB4OyBoZWlnaHQ6IDI2MnB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM1ZDBcdWMxMWMgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWNmZmNcdWI5YWMgJFEkXHVhYzFjXHViOTdjIFx1YzIxOFx1ZDU4OVx1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kbCBcXCwgciQ6ICRsJFx1YmM4OFx1YzlmOCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWJkODBcdWQxMzAgJHIkXHViYzg4XHVjOWY4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YWU0Y1x1YzljMFx1YjljYyBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHViMTEzXHVjNzc0XHVhYzAwIFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YzIxOCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM1ZDBcdWMxMWMgXHVhYzAxIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICROJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggJEhfMSwgSF8yLCBcXGNkb3RzLCBIX04kXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNmZmNcdWI5YWNcdWM3NTggXHVjMjE4ICRRJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkUSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1Y2ZmY1x1YjlhY1x1YjRlNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRsJCwgJHIkXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSBcdWNmZmNcdWI5YWNcdWM3NTggXHVjODE1XHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDFcXGxlcSBOLFFcXGxlcSAxMF41JDxcL2xpPlxyXG5cdDxsaT4kMVxcbGVxIEhfaVxcbGVxIDEwXjkkPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgbFxcbGVxIHJcXGxlcSBOJDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kUSBcXGxlcSAzMDAkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kSF8xICZsdDsgSF8yICZsdDsgXFxjZG90cyAmbHQ7IEhfTiQ8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPiRpXFxuZXEgaiBcXFJpZ2h0YXJyb3cgSF9pIFxcbmVxIEhfaiQ8XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPlx1Y2Q5NFx1YWMwMCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0IFx1YzVjNlx1Yzc0YzxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMxNDQwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFyZ2VzdCBSZWN0YW5nbGUgaW4gYSBIaXN0b2dyYW0gYW5kIFF1ZXJpZXMgMiIsImRlc2NyaXB0aW9uIjoiPGJsb2NrcXVvdGU+XHJcbjxwPlN0dWR5IG5hdHVyZSBhbmQgZmluZCBwcm9ibGVtcyBpbiZuYnNwO3RoZSB3b3JsZC48XC9wPlxyXG48XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+VGhlIHNlbnRlbmNlIGFib3ZlIGlzIGZyb20gdGhlIG1vdHRvIG9mJm5ic3A7S1NBIFZpc2lvbiAyMDQwLjxcL3A+XHJcblxyXG48cD5UbyBjZWxlYnJhdGUgZ3JhZHVhdGluZyBmcm9tIEtTQSwgdGhpcyBwcm9ibGVtIHNldHRlciBkZWNpZGVkIHRvIGNvcHkgdGhlIHByb2JsZW0gPGEgaHJlZj1cIlwvcHJvYmxlbVwvMTY5NzdcIj4xNjk3NzxcL2E+LjxcL3A+XHJcblxyXG48cD5BIGhpc3RvZ3JhbSBpcyBhIHBvbHlnb24gdGhhdCBjb25zaXN0cyBvZiByZWN0YW5nbGVzIGFsaWduZWQgYXQgYSBjb21tb24gYmFzZWxpbmUuIFRoZSByZWN0YW5nbGVzIGhhdmUgd2lkdGhzIG9mICQxJCZuYnNwO2J1dCBtYXkgaGF2ZSBkaWZmZXJlbnQgaGVpZ2h0cy4gRm9yIGV4YW1wbGUsIHRoZSBmaWd1cmUgb24gdGhlIGxlZnQgc2hvd3MgdGhlIGhpc3RvZ3JhbSB0aGF0IGNvbnNpc3RzIG9mIHJlY3RhbmdsZXMgd2l0aCB0aGUgaGVpZ2h0cyAkMywgNSwgOCwgOCwgNCwgNyQsIG1lYXN1cmVkIGluIHVuaXRzIHdoZXJlICQxJCBpcyB0aGUgd2lkdGggb2YgdGhlIHJlY3RhbmdsZXM6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3UuYWNtaWNwYy5uZXRcL2VmOWNjMDYwLTUxODYtNGRmYi1hODE0LWUyMjY2ZmIxNmUyZVwvaGlzdG9fMS53ZWJwXCIgc3R5bGU9XCJ3aWR0aDogMzU5cHg7IGhlaWdodDogMjYycHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPkRvIHRoZSBmb2xsb3dpbmcgcXVlcnkgZm9yICRRJCB0aW1lczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kbCBcXCwgciQ6IHByaW50IHRoZSBhcmVhIG9mIHRoZSBsYXJnZXN0IHJlY3RhbmdsZSBhbGlnbmVkIGF0IHRoZSBjb21tb24gYmFzZWxpbmUsIHdoaWNoIGZpdHMgaW4gYSBzdWItaGlzdG9ncmFtIGNvbnNpc3Rpbmcgb2YgdGhlICRsJC10aCByZWN0YW5nbGUgdG8gdGhlICRyJC10aCByZWN0YW5nbGUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgJE4kLCB0aGUgbnVtYmVyIG9mIHJlY3RhbmdsZXMgaW4gdGhlIGhpc3RvZ3JhbS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zICROJCBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJEhfMSwgSF8yLCBcXGNkb3RzLCBIX04kIHdoaWNoIHJlcHJlc2VudCB0aGUgaGVpZ2h0IG9mIGVhY2ggcmVjdGFuZ2xlIGluIHRoZSBoaXN0b2dyYW0uPFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zICRRJCwmbmJzcDt0aGUgbnVtYmVyIG9mIHF1ZXJpZXMuPFwvcD5cclxuXHJcbjxwPiRRJCBsaW5lcyBmb2xsb3csIGVhY2ggY29udGFpbmluZyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICRsJCBhbmQgJHIkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBhbnN3ZXJzIHRvIHRoZSBwcm9ibGVtIG9uICRRJCBsaW5lcy4gRm9yIHRoZSAkaSQtdGggbGluZSwgcHJpbnQgdGhlIGFuc3dlciBvZiB0aGUgJGkkLXRoIHF1ZXJ5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDFcXGxlcSBOLFFcXGxlcSAxMF41JDxcL2xpPlxyXG5cdDxsaT4kMVxcbGVxIEhfaVxcbGVxIDEwXjkkPFwvbGk+XHJcblx0PGxpPiQxXFxsZXEgbFxcbGVxIHJcXGxlcSBOJDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kUSBcXGxlcSAzMDAkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kSF8xICZsdDsgSF8yICZsdDsgXFxjZG90cyAmbHQ7IEhfTiQ8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPiRpXFxuZXEgaiBcXFJpZ2h0YXJyb3cgSF9pIFxcbmVxIEhfaiQ8XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPk5vIGFkZGl0aW9uYWwgY29uc3RyYWludHM8XC9wPlxyXG4ifV0=