시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 512 MB344906724.723%

문제

IOI 国の歴史の研究の第一人者であるジョイ教授のもとに,古代の IOI 国の住民が書いたとされる日記が 届いた.ジョイ教授はこの日記から古代の IOI 国における生活を研究するため,日記に書かれている出来 事を調査することにした.

この日記では N 日間に起きた出来事がそれぞれ 1 日あたり 1 つずつ書かれている.出来事は何種類かに 分類されている.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 5 j 5 Q) に,j 番目のクエリに対する重要度の最大値を表す整数を 出力せよ.

제한

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

서브태스크 1 (5점)

  • N ≤ 100.
  • Q ≤ 100.

서브태스크 2 (10점)

  • N ≤ 5 000.
  • Q ≤ 5 000.

서브태스크 3 (25점)

  • Ai ≤ Aj ≤ Bj ≤ Bi なる i, j (1 ≤ i ≤ Q, 1 ≤ j ≤ Q, i , j) は存在しない.

서브태스크 4 (60점)

追加の制限はない.

예제 입력 1

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

예제 출력 1

9
8
8
16
16
  • この日記は 5 日間からなり,日記に書かれている出来事の種類は 7, 8, 9 のいずれかである.
  • 1 日目から 2 日目において,出来事の種類 7 の重要度は 7×0 = 0,出来事の種類 8 の重要度は 8×1 = 8, 出来事の種類 9 の重要度は 9 × 1 = 9 であるから,これらのうちの最大値は 9 である.
  • 3 日目から 4 日目において,出来事の種類 7 の重要度は 7×1 = 7,出来事の種類 8 の重要度は 8×1 = 8, 出来事の種類 9 の重要度は 9 × 0 = 0 であるから,これらのうちの最大値は 8 である.
  • 4 日目において,出来事の種類 7 の重要度は 7 × 0 = 0,出来事の種類 8 の重要度は 8 × 1 = 8,出来 事の種類 9 の重要度は 9 × 0 = 0 であるから,これらのうちの最大値は 8 である.
  • 1日目から4日目において,出来事の種類7の重要度は7×1 = 7,出来事の種類8の重要度は8×2 = 16, 出来事の種類 9 の重要度は 9 × 1 = 9 であるから,これらのうちの最大値は 16 である.
  • 2日目から4日目において,出来事の種類7の重要度は7×1 = 7,出来事の種類8の重要度は8×2 = 16, 出来事の種類 9 の重要度は 9 × 0 = 0 であるから,これらのうちの最大値は 16 である.

예제 입력 2

8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

예제 출력 2

27
18
19
19

예제 입력 3

12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

예제 출력 3

18
18
9
30
18
15
17
30
18
15
18
16
30
15
15

채점 및 기타 정보

  • 예제는 채점하지 않는다.