class Doubly_Linked_List:
    def __init__(self, N):
        self.__N=N
        self.__front=[-1]*N
        self.__back=[-1]*N

    def __len__(self):
        return self.__N

    def __str__(self):
        res=[]
        used=[0]*self.__N

        for x in range(self.__N):
            if used[x]:
                continue

            a=self.enumerate(x)
            for y in a:
                used[y]=1
            res.append(a)
        return str(res)

    def __repr__(self):
        return "[Doubly Linked List]: "+str(self)

    def previous(self, x, default=-1):
        return self.__front[x] if self.__front[x]!=-1 else default

    def next(self, x, default=-1):
        return self.__back[x] if self.__back[x]!=-1 else default

    def disconnect_front(self, x):
        """ x から前に伸びるリンクを削除する.

        """

        front=self.__front; back=self.__back

        y=front[x]
        if y>=0:
            front[x]=-1
            back[y]=-1

    def disconnect_back(self, x):
        """ x から後ろに伸びるリンクを削除する.

        """

        front=self.__front; back=self.__back

        y=back[x]
        if y>=0:
            back[x]=-1
            front[y]=-1

    def extract(self, x):
        """ x に接続するリンクを削除し, x の前後が存在するならば, それらをつなぐ.
        """

        a=self.__front[x]
        b=self.__back[x]

        self.disconnect_front(x)
        self.disconnect_back(x)

        if a!=-1 and b!=-1:
            self.connect(a,b)

    def connect(self, x, y):
        """ x から y へのリンクを生成する (すでにある x からのリンクと y へのリンクは削除される).

        """

        self.disconnect_back(x)
        self.disconnect_front(y)
        self.__back[x]=y
        self.__front[y]=x

    def insert_front(self, x, y):
        """ x の前に y を挿入する.

        """

        z=self.__front[x]
        self.connect(y,x)
        if z!=-1:
            self.connect(z,y)

    def insert_back(self, x, y):
        """ x の後に y を挿入する.

        """

        z=self.__back[x]
        self.connect(x,y)
        if z!=-1:
            self.connect(y,z)

    def head(self, x):
        """ x が属する弱連結成分の先頭を求める.
        """

        while self.__front[x]!=-1:
            x=self.__front[x]
        return x

    def tail(self, x):
        """ x が属する弱連結成分の末尾を求める.
        """

        while self.__back[x]!=-1:
            x=self.__back[x]
        return x

    def enumerate(self, x):
        """ x が属している弱連結成分を先頭から順に出力する.

        """

        x=self.head(x)
        res=[x]
        while self.__back[x]>=0:
            x=self.__back[x]
            res.append(x)
        return res

    def depth(self, x):
        dep=0
        while self.__front[x]!=-1:
            x=self.__front[x]
            dep+=1
        return dep

class Binary_Indexed_Tree():
    def __init__(self, L, op, zero, neg):
        """ op を演算とする N 項の Binary Indexed Tree を作成
        op: 演算 (2変数関数, 可換群)
        zero: 群 op の単位元 (x+e=e+x=x を満たす e)
        neg : 群 op の逆元 (1変数関数, x+neg(x)=neg(x)+x=e をみたす neg(x))
        """
        self.op=op
        self.zero=zero
        self.neg=neg
        self.N=N=len(L)
        self.log=N.bit_length()-1

        X=[zero]*(N+1)

        for i in range(N):
            p=i+1
            X[p]=op(X[p],L[i])
            q=p+(p&(-p))
            if q<=N:
                X[q]=op(X[q], X[p])
        self.data=X

    def get(self, k):
        """ 第 k 要素の値を出力する.

        k    : 数列の要素
        index: 先頭の要素の番号
        """
        return self.sum(k, k)

    def add(self, k, x):
        """ 第 k 要素に x を加え, 更新を行う.

        k    : 数列の要素
        x    : 加える値
        """
        data=self.data; op=self.op
        p=k+1
        while p<=self.N:
            data[p]=op(self.data[p], x)
            p+=p&(-p)

    def update(self, k, x):
        """ 第 k 要素を x に変え, 更新を行う.

        k: 数列の要素
        x: 更新後の値
        """

        a=self.get(k)
        y=self.op(self.neg(a), x)

        self.add(k,y)

    def sum(self, l, r):
        """ 第 l 要素から第 r 要素までの総和を求める.
        ※ l != 0 を使うならば, 群でなくてはならない.
        l: 始まり
        r: 終わり
        """
        l=l+1 if 0<=l else 1
        r=r+1 if r<self.N else self.N

        if l>r:
            return self.zero
        elif l==1:
            return self.__section(r)
        else:
            return self.op(self.neg(self.__section(l-1)), self.__section(r))

    def __section(self, x):
        """ B[0]+...+B[x] を求める. """
        data=self.data; op=self.op
        S=self.zero
        while x>0:
            S=op(data[x], S)
            x-=x&(-x)
        return S

    def all_sum(self):
        return self.sum(0, self.N-1)

    def binary_search(self, cond):
        """ cond(B[0]+...+B[k]) が True となるような最小の k を返す.

        cond: 単調増加

        ※ cond(zero)=True の場合の返り値は -1 とする.
        ※ cond(B[0]+...+B[k]) なる k が (0<=k<N に) 存在しない場合の返り値は N とする.
        """

        if cond(self.zero):
            return -1

        j=0
        r=self.N
        t=1<<self.log
        data=self.data; op=self.op
        alpha=self.zero

        while t>0:
            if j+t<=self.N:
                beta=op(alpha, data[j+t])
                if not cond(beta):
                    alpha=beta
                    j+=t
            t>>=1

        return j

    def __getitem__(self, index):
        if isinstance(index, int):
            return self.get(index)
        else:
            return [self.get(t) for t in index]

    def __setitem__(self, index, val):
        self.update(index, val)

    def __iter__(self):
        for k in range(self.N):
            yield self.sum(k, k)

#==================================================
def solve():
    from operator import add, neg
    from collections import defaultdict

    N = int(input())
    A = [0] + list(map(int, input().split()))

    length = N
    Q = int(input())
    Query = []
    for _ in range(Q):
        q, *value = map(int, input().split())
        if q == 1:
            length += 1
        Query.append((q, *value))

    L = Doubly_Linked_List(length + 2)
    start = 0; goal = length + 1
    for i in range(1, N + 1):
        L.connect(i - 1, i)
    L.connect(N, goal)

    index = defaultdict(list)
    for i,a in enumerate(A[1:], 1):
        index[a].append(i)

    j = N
    for q, *value in Query:
        if q == 1:
            x, y = value

            if x != -1:
                i = index[x][-1]
            else:
                i = 0

            j += 1
            k = L.next(i)
            L.connect(i, j)
            L.connect(j, k)

            index[y].append(j)

    L_inv = [0] * (length + 2); ind = 0
    for k in range(length + 2):
        L_inv[ind] = k
        ind = L.next(ind)

    index_inv = {v: [L_inv[x] for x in index[v]][::-1] for v in index}

    B = Binary_Indexed_Tree([0] * (length + 2), add, 0, neg)
    for i, a in enumerate(A[1:], 1):
        B.add(index_inv[a][-1], a)

    ans = []
    for q, *value in Query:
        if q == 1:
            x, y = value
            B.add(index_inv[y][-1], y)
        elif q == 2:
            x, = value
            B.add(index_inv[x][-1], -x)
            index_inv[x].pop()
        else:
            x, y = value
            s = index_inv[x][-1]; t = index_inv[y][-1]
            l = min(s, t); r = max(s, t)
            ans.append(B.sum(l, r))

    return ans

#==================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write

write("\n".join(map(str, solve())))