using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Text;
using System.Linq;

using E = System.Linq.Enumerable;

internal partial class Solver {
    public void Run() {
        var n = ni();
        var q = ni();
        var c = ni(n).Select(x => x - 1).ToArray();
        var l = new int[q];
        var r = new int[q];
        for (int i = 0; i < q; i++) {
            l[i] = ni() - 1;
            r[i] = ni() - 1;
        }

        var lastIndex = E.Repeat(-1, n).ToArray();
        var prevSameColorIndex = E.Repeat(-1, n).ToArray();

        for (int i = 0; i < n; i++) {
            prevSameColorIndex[i] = lastIndex[c[i]] + 1;
            lastIndex[c[i]] = i;
        }

        var ans = new int[q];

        var tree = new WaveletTree(n + 10);

        tree.Init(prevSameColorIndex);

        for (int i = 0; i < q; i++) {
            var count = tree.RankLessThan(l[i] + 1, r[i] + 1);
            count -= tree.RankLessThan(l[i], l[i]);
            ans[i] = count;
        }

        cout.WriteLine(ans.JoinToString("\n"));
    }
}

public class WaveletTree {
    private class BitArray {
        private const int BlockBitCount = 64;
        private const int TableBlockCount = 4;

        private readonly List<int> rankTable = new List<int>();
        private readonly List<ulong> bitBlocks;
        private int oneNum;

        private static int PopCount(ulong x) {
            x = (x & 0x5555555555555555UL) + ((x >> 1) & 0x5555555555555555UL);
            x = (x & 0x3333333333333333UL) + ((x >> 2) & 0x3333333333333333UL);
            x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fUL;
            x = x + (x >> 8);
            x = x + (x >> 16);
            x = x + (x >> 32);
            return (int)(x & 0x7FLU);
        }

        private static int PopCountWithMask(ulong x, int offset) {
            if (offset == 0) {
                return 0;
            }

            return PopCount(x & ((1LU << offset) - 1));
        }

        public BitArray(int n = 0) {
            Count = n;
            oneNum = 0;
            int blockNum = (Count + BlockBitCount - 1) / BlockBitCount;
            bitBlocks = new List<ulong>(blockNum);
            for (int i = 0; i < blockNum; i++) {
                bitBlocks.Add(0);
            }
        }

        public int Count { get; private set; }

        public void Add(bool bit) {
            Count++;
            int last = Count - 1;
            if (last / BlockBitCount == bitBlocks.Count) {
                bitBlocks.Add(0UL);
                int table_num = ((bitBlocks.Count + TableBlockCount - 1) / TableBlockCount) + 1;
                while (rankTable.Count < table_num) {
                    rankTable.Add(rankTable.Count > 0 ? rankTable[rankTable.Count - 1] : 0);
                }
            }
            SetBit(bit, last);
            if (bit) {
                rankTable[rankTable.Count - 1]++;
                oneNum++;
            }
        }

        public void RemoveBack() {
            int last = Count - 1;
            if (Get(last)) {
                oneNum--;
                rankTable[rankTable.Count - 1]--;
            }
            SetBit(false, last);
            last--;
            if (last / BlockBitCount + 1 < bitBlocks.Count) {
                bitBlocks.RemoveAt(bitBlocks.Count - 1);
                int table_num = ((bitBlocks.Count + TableBlockCount - 1) / TableBlockCount) + 1;
                while (rankTable.Count > table_num) {
                    rankTable.RemoveAt(rankTable.Count - 1);
                }
            }
            Count--;
        }

        public void Build() {
            int table_num = ((bitBlocks.Count + TableBlockCount - 1) / TableBlockCount) + 1;
            for (int i = 0; i < table_num; i++) {
                rankTable.Add(0);
            }

            oneNum = 0;
            for (int i = 0; i < bitBlocks.Count; i++) {
                if (i % TableBlockCount == 0) {
                    rankTable[i / TableBlockCount] = oneNum;
                }
                oneNum += PopCount(bitBlocks[i]);
            }
            rankTable[rankTable.Count - 1] = oneNum;
        }

        public void SetBit(bool bit, int pos) {
            if (bit) {
                bitBlocks[pos / BlockBitCount] |= (1LU << (pos % BlockBitCount));
            } else {
                bitBlocks[pos / BlockBitCount] &= ~(1LU << (pos % BlockBitCount));
            }
        }

        public int Rank(int pos) {
            int blockIndex = pos / BlockBitCount;
            int tableIndex = blockIndex / TableBlockCount;
            int rank = rankTable[tableIndex];
            for (int i = tableIndex * TableBlockCount; i < blockIndex; i++) {
                rank += PopCount(bitBlocks[i]);
            }
            if (blockIndex < bitBlocks.Count) {
                rank += PopCountWithMask(bitBlocks[blockIndex], pos % BlockBitCount);
            }
            return rank;
        }

        public int Rank(bool bit, int pos) {
            return bit ? Rank(pos) : pos - Rank(pos);
        }
        public void Rank(int pos, out int rank0, out int rank1) {
            rank1 = Rank(pos);
            rank0 = pos - rank1;
        }

        public int Select(bool bit, int rank) {
            int blockPos = SelectOutBlock(bit, ref rank);
            ulong blockBit = bitBlocks[blockPos];
            if (!bit) {
                blockBit = ~blockBit;
            }

            return blockPos * BlockBitCount + SelectInBlock(blockBit, rank);
        }

        public bool Get(int pos) {
            return ((bitBlocks[pos / BlockBitCount] >> (pos % BlockBitCount)) & 1) != 0;
        }

        public int GetOneNum() {
            return oneNum;
        }

        public int GetZeroNum() {
            return Count - oneNum;
        }

        private int SelectOutBlock(bool bit, ref int rank) {
            int left = 0, right = rankTable.Count - 1;
            int tableIndex = 0;
            while (left <= right) {
                int mid = (left + right) / 2;
                int bitLength = (BlockBitCount * TableBlockCount * mid);
                int bitNum = bit ? rankTable[mid] : bitLength - rankTable[mid];
                if (bitNum < rank) {
                    tableIndex = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            int blockPos = tableIndex * TableBlockCount;
            rank -= bit ? rankTable[tableIndex] : blockPos * BlockBitCount - rankTable[tableIndex];

            for (; blockPos < bitBlocks.Count; blockPos++) {
                int nextRank = bit ? PopCount(bitBlocks[blockPos]) : BlockBitCount - PopCount(bitBlocks[blockPos]);
                if (rank <= nextRank) {
                    break;
                }

                rank -= nextRank;
            }
            return blockPos;
        }

        private static int SelectInBlock(ulong x, int rank) {
            ulong x1 = x - ((x & 0xAAAAAAAAAAAAAAAALU) >> 1);
            ulong x2 = (x1 & 0x3333333333333333LU) + ((x1 >> 2) & 0x3333333333333333LU);
            ulong x3 = (x2 + (x2 >> 4)) & 0x0F0F0F0F0F0F0F0FLU;

            int pos = 0;
            for (; ; pos += 8) {
                int rank_next = (int)((x3 >> pos) & 0xFFLU);
                if (rank <= rank_next) {
                    break;
                }

                rank -= rank_next;
            }

            int v2 = (int)((x2 >> pos) & 0xFL); if (rank > v2) { rank -= v2; pos += 4; }
            int v1 = (int)((x1 >> pos) & 0x3L); if (rank > v1) { rank -= v1; pos += 2; }
            int v0 = (int)((x >> pos) & 0x1L); if (rank > v0) { rank -= v0; pos += 1; }

            return pos;
        }
    };
    private readonly int BitNum;
    public int Length { get; private set; }

    private readonly BitArray[] bitArray;

    private static int Left(int x) { return (x * 2) + 1; }

    private static int Right(int x) { return (x * 2) + 2; }

    public WaveletTree(int maxValue) {
        BitNum = 1;
        while ((1 << BitNum) < maxValue) {
            BitNum++;
        }

        bitArray = new BitArray[1 << (BitNum + 1)];
    }

    public void Init(int[] array) {
        Length = array.Length;
        Init(0, BitNum - 1, array);
    }

    private void Init(int index, int bitPos, IList<int> array) {
        if (array.Count == 0) {
            return;
        }

        var b = GetBitArrayOrCreate(index, array.Count);
        var zero = new List<int>();
        var one = new List<int>();
        for (int i = 0; i < array.Count; i++) {
            if ((array[i] & (1 << bitPos)) != 0) {
                one.Add(array[i]);
                b.SetBit(true, i);
            } else {
                zero.Add(array[i]);
                b.SetBit(false, i);
            }
        }
        b.Build();

        if (bitPos - 1 >= 0) {
            Init(Left(index), bitPos - 1, zero);
            Init(Right(index), bitPos - 1, one);
        }
    }

    private BitArray GetBitArrayOrCreate(int index, int n = 0) {
        return bitArray[index] ?? (bitArray[index] = new BitArray(n));
    }

    /// <summary>
    /// return k-th value (0-origin)
    /// </summary>
    public int Access(int k) {
        return Access(k, 0, BitNum - 1);
    }

    private int Access(int k, int index, int bitPos) {
        if (bitPos < 0) {
            return 0;
        }

        var b = bitArray[index];
        if (b == null || b.Count == 0) {
            return 0;
        }

        if (b.Get(k)) {
            return Access(b.Rank(true, k), Right(index), bitPos - 1) | (1 << bitPos);
        } else {
            return Access(b.Rank(false, k), Left(index), bitPos - 1);
        }
    }

    public void Add(int x) {
        Add(x, 0, BitNum - 1);
        Length++;
    }

    private void Add(int x, int index, int bitPos) {
        if (bitPos < 0) {
            return;
        }

        var b = GetBitArrayOrCreate(index);
        bool bit = (x & (1 << bitPos)) != 0;
        b.Add(bit);
        Add(x, bit ? Right(index) : Left(index), bitPos - 1);
    }

    public void RemoveBack() {
        RemoveBack(0, BitNum - 1);
        Length--;
    }

    private void RemoveBack(int index, int bitPos) {
        if (bitPos < 0) {
            return;
        }

        var b = GetBitArrayOrCreate(index);
        bool bit = b.Get(b.Count - 1);
        b.RemoveBack();
        if (bit) {
            RemoveBack(Right(index), bitPos - 1);
        } else {
            RemoveBack(Left(index), bitPos - 1);
        }
    }

    public void RankAll(int c, int pos, out int rank, out int rankLessThan, out int rankMoreThan) {
        rankLessThan = 0;
        rankMoreThan = 0;
        RankAll(c, pos, 0, BitNum - 1, ref rankLessThan, ref rankMoreThan);
        rank = pos - rankMoreThan - rankLessThan;
    }

    private void RankAll(int c, int pos, int index, int bitPos, ref int rankLessThan, ref int rankMoreThan) {
        if (bitPos < 0) {
            return;
        }

        var b = bitArray[index];
        if (b == null || b.Count == 0) {
            return;
        }

        int pos0Num, pos1Num;
        b.Rank(pos, out pos0Num, out pos1Num);
        if ((c & (1 << bitPos)) != 0) {
            rankLessThan += pos0Num;
            RankAll(c, pos1Num, Right(index), bitPos - 1, ref rankLessThan, ref rankMoreThan);
        } else {
            rankMoreThan += pos1Num;
            RankAll(c, pos0Num, Left(index), bitPos - 1, ref rankLessThan, ref rankMoreThan);
        }
    }

    /// <summary>
    /// return the number of occurrences of c in [0,pos)
    /// </summary>
    public int Rank(int c, int pos) {
        int rank, more, less;
        RankAll(c, pos, out rank, out less, out more);
        return rank;
    }

    public int RankMoreThan(int c, int pos) {
        int rank, more, less;
        RankAll(c, pos, out rank, out less, out more);
        return more;
    }

    public int RankLessThan(int c, int pos) {
        int rank, more, less;
        RankAll(c, pos, out rank, out less, out more);
        return less;
    }

    /// <summary>
    /// return min value in [begin,end)
    /// </summary>
    public int MinRange(int begin, int end) {
        return Quantile(begin, end, 1);
    }

    /// <summary>
    /// return max value in [begin,end)
    /// </summary>
    public int MaxRange(int begin, int end) {
        return Quantile(begin, end, end - begin);
    }

    /// <summary>
    /// return k-th value in [begin,end)
    /// k is 1-index
    /// </summary>
    public int Quantile(int begin, int end, int k) {
        return Quantile(begin, end, k, 0, BitNum - 1);
    }

    private int Quantile(int begin, int end, int k, int index, int bitPos) {
        if (bitPos < 0) {
            return 0;
        }

        var b = bitArray[index];
        if (b == null || b.Count == 0) {
            return 0;
        }

        int begin0Num, begin1Num, end0Num, end1Num;
        b.Rank(begin, out begin0Num, out begin1Num);
        b.Rank(end, out end0Num, out end1Num);
        int range0Num = end0Num - begin0Num;
        if (k <= range0Num) {
            return Quantile(begin0Num, end0Num, k, Left(index), bitPos - 1);
        } else {
            return Quantile(begin1Num, end1Num, k - range0Num, Right(index), bitPos - 1) | (1 << bitPos);
        }
    }

    public int FreqRange(int begin, int end, int minValue, int maxValue) // [min,max)
    {
        if (minValue >= maxValue) {
            return 0;
        }

        if (begin >= end) {
            return 0;
        }

        return RankLessThan(maxValue, end) - RankLessThan(minValue, end)
            - RankLessThan(maxValue, begin) + RankLessThan(minValue, begin);
    }


    public int XorMax(int begin, int end, int x) {
        return XorMax(begin, end, x, 0, BitNum - 1);
    }

    private int XorMax(int begin, int end, int x, int index, int bitPos) {
        if (bitPos < 0) {
            return 0;
        }

        var b = bitArray[index];
        if (b == null || b.Count == 0) {
            return 0;
        }

        int begin0Num, begin1Num, end0Num, end1Num;
        b.Rank(begin, out begin0Num, out begin1Num);
        b.Rank(end, out end0Num, out end1Num);
        int range0Num = end0Num - begin0Num;
        int range1Num = end - begin - range0Num;
        if ((x & (1 << bitPos)) != 0) { // choose 0
            if (range0Num > 0) {
                return XorMax(begin0Num, end0Num, x, Left(index), bitPos - 1);
            } else {
                return XorMax(begin1Num, end1Num, x, Right(index), bitPos - 1) | (1 << bitPos);
            }
        } else {
            if (range1Num > 0) {
                return XorMax(begin1Num, end1Num, x, Right(index), bitPos - 1) | (1 << bitPos);
            } else {
                return XorMax(begin0Num, end0Num, x, Left(index), bitPos - 1);
            }
        }
    }
};
// PREWRITEN CODE BEGINS FROM HERE

static public class StringExtensions {
    static public string JoinToString<T>(this IEnumerable<T> source, string separator = " ") {
        return string.Join(separator, source);
    }
}

internal partial class Solver : Scanner {
    public static void Main() {
#if LOCAL
        byte[] inputBuffer = new byte[1000000];
        var inputStream = Console.OpenStandardInput(inputBuffer.Length);
        using (var reader = new StreamReader(inputStream, Console.InputEncoding, false, inputBuffer.Length)) {
            Console.SetIn(reader);
            new Solver(Console.In, Console.Out).Run();
        }
#else
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        new Solver(Console.In, Console.Out).Run();
        Console.Out.Flush();
#endif
    }

#pragma warning disable IDE0052
    private readonly TextReader cin;
    private readonly TextWriter cout;
    private readonly TextWriter cerr;
#pragma warning restore IDE0052

    public Solver(TextReader reader, TextWriter writer)
        : base(reader) {
        cin = reader;
        cout = writer;
        cerr = Console.Error;
    }

    public Solver(string input, TextWriter writer)
        : this(new StringReader(input), writer) {
    }

#pragma warning disable IDE1006
#pragma warning disable IDE0051
    private int ni() { return NextInt(); }
    private int[] ni(int n) { return NextIntArray(n); }
    private long nl() { return NextLong(); }
    private long[] nl(int n) { return NextLongArray(n); }
    private double nd() { return NextDouble(); }
    private double[] nd(int n) { return NextDoubleArray(n); }
    private string ns() { return Next(); }
    private string[] ns(int n) { return NextArray(n); }
#pragma warning restore IDE1006
#pragma warning restore IDE0051
}

#if DEBUG
internal static class LinqPadExtension {
    public static string TextDump<T>(this T obj) {
        if (obj is IEnumerable) return (obj as IEnumerable).Cast<object>().JoinToString().Dump();
        else return obj.ToString().Dump();
    }
    public static T Dump<T>(this T obj) {
        return LINQPad.Extensions.Dump(obj);
    }
}
#endif

public class Scanner {
    private readonly TextReader Reader;
    private readonly CultureInfo ci = CultureInfo.InvariantCulture;

    private readonly char[] buffer = new char[2 * 1024];
    private int cursor = 0, length = 0;
    private string Token;
    private readonly StringBuilder sb = new StringBuilder(1024);

    public Scanner()
        : this(Console.In) {
    }

    public Scanner(TextReader reader) {
        Reader = reader;
    }

    public int NextInt() { return checked((int)NextLong()); }
    public long NextLong() {
        var s = Next();
        long r = 0;
        int i = 0;
        bool negative = false;
        if (s[i] == '-') {
            negative = true;
            i++;
        }
        for (; i < s.Length; i++) {
            r = r * 10 + (s[i] - '0');
#if DEBUG
            if (!char.IsDigit(s[i])) throw new FormatException();
#endif
        }
        return negative ? -r : r;
    }
    public double NextDouble() { return double.Parse(Next(), ci); }
    public string[] NextArray(int size) {
        string[] array = new string[size];
        for (int i = 0; i < size; i++) {
            array[i] = Next();
        }

        return array;
    }
    public int[] NextIntArray(int size) {
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = NextInt();
        }

        return array;
    }

    public long[] NextLongArray(int size) {
        long[] array = new long[size];
        for (int i = 0; i < size; i++) {
            array[i] = NextLong();
        }

        return array;
    }

    public double[] NextDoubleArray(int size) {
        double[] array = new double[size];
        for (int i = 0; i < size; i++) {
            array[i] = NextDouble();
        }

        return array;
    }

    public string Next() {
        if (Token == null) {
            if (!StockToken()) {
                throw new Exception();
            }
        }
        var token = Token;
        Token = null;
        return token;
    }

    public bool HasNext() {
        if (Token != null) {
            return true;
        }

        return StockToken();
    }

    private bool StockToken() {
        while (true) {
            sb.Clear();
            while (true) {
                if (cursor >= length) {
                    cursor = 0;
                    if ((length = Reader.Read(buffer, 0, buffer.Length)) <= 0) {
                        break;
                    }
                }
                var c = buffer[cursor++];
                if (33 <= c && c <= 126) {
                    sb.Append(c);
                } else {
                    if (sb.Length > 0) break;
                }
            }

            if (sb.Length > 0) {
                Token = sb.ToString();
                return true;
            }

            return false;
        }
    }
}

Measured memory_bytes: 195040