역사 연구

IOI국의 역사 연구의 최고 권위자인 조이 교수에게 고대 IOI국 주민이 쓴 것으로 보이는 일기가 도착했다. 조이 교수는 이 일기로 고대 IOI국의 생활을 연구하려고, 일기에 적힌 사건을 조사하기로 했다.

이 일기에는 N일 동안 일어난 사건이 하루에 하나씩 적혀 있다. 사건은 몇 가지 종류로 분류된다. i일째 (1 ≤ i ≤ N) 사건의 종류는 정수 Xi로 나타낸다. Xi 값이 클수록 규모가 큰 사건이라고 여긴다.

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

1. 일기의 N일 중 연속한 며칠을 분석할 기간으로 고른다.
2. 사건 종류 t의 중요도를 t × (그 기간에서 종류 t인 사건의 개수)로 한다.
3. 모든 사건 종류에 대해 중요도를 계산하고, 그 최댓값을 구한다.

당신은 조이 교수로부터 분석 프로그램을 만들라는 명령을 받았다. 이 프로그램은 분석할 기간이 주어졌을 때 중요도의 최댓값을 구할 수 있어야 한다.

일기의 N일 동안 사건 종류와 일기에서의 기간을 나타내는 쿼리 Q개가 주어졌을 때, 각 쿼리마다 사건 중요도의 최댓값을 구하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다.

• 1번째 줄에는 정수 N, Q가 공백을 구분으로 적혀 있다. 이는 일기가 N일 분량 있고 쿼리가 Q개 주어진다는 뜻이다.
• 다음 줄에는 N개의 정수 X1, ..., XN이 공백을 구분으로 적혀 있으며, Xi (1 ≤ i ≤ N)는 i일째 사건의 종류를 나타낸다.
• 이어지는 Q개 줄 중 j번째 줄 (1 ≤ j ≤ Q)에는 정수 Aj, Bj (1 ≤ Aj ≤ Bj ≤ N)가 공백을 구분으로 적혀 있으며, j번째 쿼리가 Aj일째부터 Bj일째까지의 기간에 대한 것임을 나타낸다.

표준 출력에 Q줄을 출력하라. j번째 줄 (1 ≤ j ≤ Q)에 j번째 쿼리에 대한 중요도의 최댓값을 나타내는 정수를 출력하라.

• 1 ≤ N ≤ 100 000.
• 1 ≤ Q ≤ 100 000.
• 1 ≤ Xi ≤ 1 000 000 000 (1 ≤ i ≤ N).