'''
本质还是莫队算法，只不过除了区间左右位置以外，还需要
多维护一个时间维度，所以是三维的莫队
'''




import math

n, m = map(int, input().split())
arr = list(map(int, input().split()))
new_arr = arr[::]
part_len = int(math.sqrt(n))


rec = [(None, None, None)] # rec[i] = (pos, old_val, new_val)表示i时刻将pos位置数值从old_val改为new_vals

t = 0
qq = []
idx = 0
for i in range(m):
    cmd, a, b = input().split()

    if cmd == 'R':
        pos, val = int(a) - 1, int(b)
        t += 1
        rec.append((pos, new_arr[pos], val))
        new_arr[pos] = val

    else:
        a, b = int(a) - 1, int(b) - 1
        qq.append((a // part_len, b // part_len, t, a, b, idx))
        idx += 1

qq.sort()
ret = [0] * idx

ii, jj, tt = 0, 0, 0
ans = 1
cnt = [0] * 1000005     # 每一个数值个数计数
cnt[arr[0]] = 1

for _, _, t, a, b, idx in qq:

    if ii > a:
        while ii != a:
            ii -= 1
            cnt[arr[ii]] += 1
            if cnt[arr[ii]] == 1:
                ans += 1

    elif ii < a:
        while ii != a:
            cnt[arr[ii]] -= 1
            if cnt[arr[ii]] == 0:
                ans -= 1
            ii += 1

    if jj < b:
        while jj != b:
            jj += 1
            cnt[arr[jj]] += 1
            if cnt[arr[jj]] == 1:
                ans += 1

    if jj > b:
        while jj != b:
            cnt[arr[jj]] -= 1
            if cnt[arr[jj]] == 0:
                ans -= 1
            jj -= 1

    if tt < t:
        while tt != t:
            tt += 1
            pos, old_val, new_val = rec[tt]
            arr[pos] = new_val      # 时间维度更新的时候同时也将数组更新
            if pos >= ii and pos <= jj:
                cnt[old_val] -= 1
                if cnt[old_val] == 0:
                    ans -= 1

                cnt[new_val] += 1
                if cnt[new_val] == 1:
                    ans += 1

    if tt > t:
        while tt != t:
            pos, old_val, new_val = rec[tt]
            tt -= 1
            arr[pos] = old_val
            if pos >= ii and pos <= jj:
                cnt[new_val] -= 1
                if cnt[new_val] == 0:
                    ans -= 1

                cnt[old_val] += 1
                if cnt[old_val] == 1:
                    ans += 1

    #print(a, b, t, ans, cnt[:10])
    ret[idx] = ans

for val in ret:
    print(val)