시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 80 32 14 46.667%

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 아래와 같은 쿼리 Q개를 수행해보자.

  • l r w: l번째 직사각형부터 r번째 직사각형까지만 있을 때, 너비가 w이면서 가장 넓이가 큰 직사각형의 높이를 출력한다.

입력

첫째 줄에 직사각형의 수 N이 주어진다. 둘째 줄에는 N개의 정수 h1, ..., hn 가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이다.

셋째 줄에는 쿼리의 수 Q가 주어진다. 넷째 줄부터 Q개의 줄에는 쿼리가 주어진다.

제한

  • 1 ≤ N, Q ≤ 100,000
  • 1 ≤ hi ≤ 1,000,000,000
  • 1 ≤ l ≤ r ≤ N
  • 1 ≤ w ≤ r-l+1

예제 입력 1

7
2 1 4 5 1 3 3
8
3 4 2
4 7 2
2 5 1
2 5 2
2 5 3
2 5 4
1 3 2
6 7 2

예제 출력 1

4
3
5
4
1
1
1
3

출처