#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
 
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
 
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define f(i, n) for(int i = 0; i < n; ++i)
#define pb push_back
#define eb emplace_back
#define m_p make_pair
#define T int t = 0; cin >> t; while(t--)
#define pr(a) for(int i = 0; i < (int)a.size(); ++i)cout << a[i] << " ";cout << endl;
#define b_e(a) a.begin(), a.end()
typedef long long ll;
typedef long double lld;
const ll mod = 1e15;
const ll mx = 2e6;
const ll inf = 1e9;
const int sz = 26;
typedef long long ll;

#define all(v) (v).begin(), (v).end()
#define LEFT(n) (n << 1)
#define RIGHT(n) ( (n << 1)|1 )

const int INSERTION = 0, QUERY = 1, MAX_N = 1e6 + 5, OLD_LAST_OCCURENCE = 0, NEW_LAST_OCCURENCE = 1;
int sum_tree[3*MAX_N];

struct info
{
    int end;
    int type;
    int position, value;
    int left, right, query_no;

    info(){ end = type = left = right = query_no = position = -1; }
};

int compare_ends(const info &A, const info &B)
{
    if(A.end < B.end)
        return true;
    else if(A.end == B.end)
        return (A.type == INSERTION);

    return false;
}

void insert(int n, int left, int right, int position, int position_type)
{
    if(right < position || position < left)
        return;

    if(left == right)
    {
        if(position_type == OLD_LAST_OCCURENCE)
            sum_tree[n] = 0;
        else if(position_type == NEW_LAST_OCCURENCE)
            sum_tree[n] = 1;

        return;
    }

    int mid = (left + right) >> 1;

    if(position <= mid)
        insert(LEFT(n), left, mid, position, position_type);
    else if(position > mid)
        insert(RIGHT(n), mid + 1, right, position, position_type);

    sum_tree[n] = sum_tree[LEFT(n)] + sum_tree[RIGHT(n)];
}

int query(int n, int left, int right, int query_left, int query_right)
{
   if(query_right < left || right < query_left)
       return 0;

    if(query_left <= left && right <= query_right)
        return sum_tree[n];

    int mid = (left + right) >> 1;

    int left_answer = query(LEFT(n), left, mid, query_left, query_right);
    int right_answer = query(RIGHT(n), mid + 1, right, query_left, query_right);

    return (left_answer + right_answer);
}

int main()
{
    memset(sum_tree, 0, sizeof(sum_tree));

    vector <info> event;

    int no_of_elements;
    int no_of_queries;
    scanf("%d", &no_of_elements);
    scanf("%d", &no_of_queries);
    for(int i = 1; i <= no_of_elements; i++)
    {
        info current_event;
        current_event.type = INSERTION;
        current_event.end = current_event.position = i;
        scanf("%d", &current_event.value);

        event.push_back(current_event);
    }

    
    
    for(int i = 1; i <= no_of_queries; i++)
    {
        info current_event;
        current_event.type = QUERY;

        scanf("%d %d", &current_event.left, &current_event.right);
        current_event.end = current_event.right;
        current_event.query_no = i;

        event.push_back(current_event);
    }

    sort(all(event), compare_ends);

    int no_of_events = no_of_elements + no_of_queries;

    map <int, int> last_occurence;
    vector <int> answer(no_of_queries + 1);

    for(int i = 0; i < no_of_events; i++)
    {
       if(event[i].type == INSERTION)
       {
           int element = event[i].value;

           if(last_occurence.count(element) == 1)
           {
               insert(1, 1, no_of_elements, last_occurence[element], OLD_LAST_OCCURENCE);
           }

           insert(1, 1, no_of_elements, event[i].position, NEW_LAST_OCCURENCE);
           last_occurence[element] = event[i].position;
       }
       else if(event[i].type == QUERY)
       {
           answer[event[i].query_no] = query(1, 1, no_of_elements, event[i].left, event[i].right);
       }
    }

    for(int i = 1; i <= no_of_queries; i++)
        printf("%d\n", answer[i]);

    return 0;
}

Measured memory_bytes: 68272