역사적 조사 Batch 컴파일 명령

IOI나라 역사의 거장 조승현 교수에게 고대 IOI나라 주민이 썼다고 하는 일기가 도착했습니다. 조승현 교수는 이 일기에서 고대의 IOI나라의 생활을 연구하기 위해 일기에 기록된 사건들을 조사하기로 했습니다.

이 일기에는 $N$일동안 일어난 사건들이 하루에 한 개씩 적혀 있습니다. 사건은 여러 개의 종류로 분류되어 있습니다. 이들 중 $i$번째 ($1 \le i \le N$) 날에 일어난 사건의 유형은 $X_{i}$로 표현되며, 이 값이 클 수록 규모가 큰 사건으로 간주됩니다.

조승현 교수는 다음과 같은 방법으로 일기를 분석하기로 했습니다.

1. 일기의 $N$일 중에서 연속하는 며칠간을 '분석 기간'으로 선택합니다.
2. 사건의 유형 $t$의 중요도를 $t \times $(이 기간 안의 종류가 $t$인 사건의 개수)로 둡니다.
3. 모든 사건 유형에 대해 중요도를 계산하고 그 최댓값을 산출합니다.

여러분은 조승현 교수가 일기를 분석할 수 있도록 프로그램을 작성해야 합니다. 이 프로그램은 분석 기간들이 주어질 때 중요도의 최댓값을 구할 수 있어야 합니다.

해야 할 일

일기에 적힌 $N$일간의 사건의 종류와 $Q$개의 분석 기간들이 주어질 때 각 분석 기간에 대해 사건의 중요도의 최댓값을 구하는 프로그램을 작성하세요.

입력 형식

표준 입력에서 다음 입력을 받습니다.

• 첫 번째 줄에 두 개의 정수 $N$과 $Q$가 공백을 사이로 두고 주어집니다. 이것은 승현이가 $N$일치의 일기를 받았고, 분석 기간이 $Q$개라는 것을 의미합니다.
• 다음 줄에는 $N$개의 정수 $X_{1}, X_{2}, \cdots, X_{N}$이 공백을 사이로 두고 주어집니다. 이 중 $X_{i}$ ($1 \le i \le N$)은 $i$번째 날의 사건 유형을 나타냅니다.
• $Q$개 줄이 주어집니다. 이 중 $j$번째 줄 ($1 \le j \le Q$)에는 두 개의 정수 $A_{j}$와 $B_{j}$ ($1 \le A_{j} \le B_{j} \le N$)이 공백을 사이로 두고 주어지는데, 이는 $j$번째 분석 기간이 $A_{j}$일째에서부터 $B_{j}$일째까지의 기간이라는 것입니다.

출력 형식

표준 출력으로 $Q$개의 줄을 출력합니다. 이 중 $j$번째 줄($1 \le j \le Q$)에는 $j$번째 분석 기간에서 중요도의 최댓값을 출력합니다.

제약 조건

모든 데이터는 아래 조건을 만족합니다.

• $1 \le N \le 100,000$
• $1 \le Q \le 100,000$
• $1 \le X_{i} \le 1,000,000,000$ ($1 \le i \le N$)

서브태스크

서브태스크 1 [5점]

• $N \le 100$
• $Q \le 100$

서브태스크 2 [10점]

• $N \le 5,000$
• $Q \le 5,000$

서브태스크 3 [25점]

• $A_{i} \le A_{j} \le B_{j} \le B_{i}$를 만족하는 $i, j$ ($1 \le i \le Q$, $1 \le j \le Q$, $i \neq j$)는 존재하지 않습니다.

서브태스크 4 [60점]

추가적인 제약 조건이 없습니다.

예제

이 일기는 5일치 분량이며 기록된 사건의 유형은 7, 8, 9 중 하나입니다.

• 1일에서 2일째까지 유형 7의 중요도는 $7 \times 0 = 0$, 유형 8의 중요도는 $8 \times 1 = 8$, 유형 9의 중요도는 $9 \times 1 = 9$입니다. 따라서 중요도의 최댓값은 9입니다.
• 3일에서 4일째까지 유형 7의 중요도는 $7 \times 1 = 7$, 유형 8의 중요도는 $8 \times 1 = 8$, 유형 9의 중요도는 $9 \times 0 = 0$입니다. 따라서 중요도의 최댓값은 8입니다.
• 4일에서 4일째까지 유형 7의 중요도는 $7 \times 0 = 0$, 유형 8의 중요도는 $8 \times 1 = 8$, 유형 9의 중요도는 $9 \times 0 = 0$입니다. 따라서 중요도의 최댓값은 8입니다.
• 1일에서 4일째까지 유형 7의 중요도는 $7 \times 1 = 7$, 유형 8의 중요도는 $8 \times 2 = 16$, 유형 9의 중요도는 $9 \times 1 = 9$입니다. 따라서 중요도의 최댓값은 16입니다.
• 2일에서 4일째까지 유형 7의 중요도는 $7 \times 1 = 7$, 유형 8의 중요도는 $8 \times 2 = 16$, 유형 9의 중요도는 $9 \times 0 = 0$입니다. 따라서 중요도의 최댓값은 16입니다.

위 예제는 서브태스크 3의 제약 조건을 만족합니다.