Module: Moアルゴリズム

Problem

長さ n の整数 A の配列が与えられます。
「インデックス l の要素からインデックス r の要素まで、配列 A のサブセグメントの異なる数の数を報告する」という形式の m 個のクエリに答える必要があります。 (サブセグメントの両方の境界が含まれ、配列は 1 から数えられます)。

入力:
最初の行には 2 つの数値が含まれます。n - 配列要素の数と m - リクエストの数 (1 <= n、m <= 10⁵)。
2 行目には n 個の整数 A_i - 配列要素 (0 <= A_i <= 10⁶) が含まれます。
次に m 行があり、それぞれに 2 つの数値 l と r が含まれます。これは、各クエリのサブセグメントの境界です (1 <= l <= r <= n)。

出力:
1 行に、スペースで区切られた m 個の数字を出力します。各クエリについて、対応するサブセグメントの異なる数字の数です。

例:
  <本体>

入力	出力
7 5 1 3 1 2 2 4 1 1 3 4 5 37 24 77	2 1 3 3 1