Serega and Fun (Codeforces 455D)
Tags: Others, data structures

Serega loves fun. However, everyone has fun in the unique manner. Serega has fun by solving query problems. One day Fedor came up with such a problem.You are given an array a consisting of n positive integers and queries to it. The queries can be of two types:  Make a unit cyclic shift to the right on the segment from l to r (both borders inclusive). That is rearrange elements of the array in the following manner:a[l], a[l + 1], ..., a[r - 1], a[r] → a[r], a[l], a[l + 1], ..., a[r - 1]. Count how many numbers equal to k are on the segment from l to r (both borders inclusive). Fedor hurried to see Serega enjoy the problem and Serega solved it really quickly. Let's see, can you solve it?

Input: The first line contains integer n (1 ≤ n ≤ 105) — the number of elements of the array. The second line contains n integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).The third line contains a single integer q (1 ≤ q ≤ 105) — the number of queries. The next q lines contain the queries.As you need to respond to the queries online, the queries will be encoded. A query of the first type will be given in format: 1 l'i r'i. A query of the second type will be given in format: 2 l'i r'i k'i. All the number in input are integer. They satisfy the constraints: 1 ≤ l'i, r'i, k'i ≤ n.To decode the queries from the data given in input, you need to perform the following transformations:li = ((l'i + lastans - 1) mod n) + 1; ri = ((r'i + lastans - 1) mod n) + 1; ki = ((k'i + lastans - 1) mod n) + 1.Where lastans is the last reply to the query of the 2-nd type (initially, lastans = 0). If after transformation li is greater than ri, you must swap these values.

Output: For each query of the 2-nd type print the answer on a single line.


Sample Inputs:
7
6 6 2 7 4 2 5
7
1 3 6
2 2 4 2
2 2 4 7
2 2 2 5
1 2 6
1 1 4
2 1 7 3

8
8 4 2 2 7 7 8 8
8
1 8 8
2 8 1 7
1 8 1
1 7 3
2 8 8 3
1 1 4
1 2 7
1 4 5

Sample Outputs:
2
1
0
0

2
0

Solution (Python):
from io import BytesIO, IOBase
import math
import random
import sys
import os
import bisect
import typing
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase, ascii_letters
from typing import *
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
n = II()
nums = LII()
block_size = query_time = 1000
m = (n - 1) // block_size + 1
blocks = [None] * m
real_blocksize = [0] * m
calcs = [None] * m

def reconstruct():
    vals = []
    try:
        for block in blocks:
            vals.extend(block)
    except:
        vals = nums
    for i in range(n):
        idx = i // block_size
        if i % block_size == 0:
            blocks[idx] = []
            real_blocksize[idx] = 0
            calcs[idx] = Counter()
        blocks[idx].append(vals[i])
        real_blocksize[idx] += 1
        calcs[idx][vals[i]] += 1

def delete(idx):
    l = 0
    for i in range(m):
        if l <= idx < l + real_blocksize[i]:
            res = blocks[i].pop(idx - l)
            real_blocksize[i] -= 1
            calcs[i][res] -= 1
            return res
        l += real_blocksize[i]

def insert(idx, val):
    l = 0
    for i in range(m):
        if l <= idx <= l + real_blocksize[i]:
            blocks[i].insert(idx - l, val)
            real_blocksize[i] += 1
            calcs[i][val] += 1
        l += real_blocksize[i]

def find(left, right, k):
    l = 0
    res = 0
    for i in range(m):
        if l > right:
            break
        if left <= l and l + real_blocksize[i] - 1 <= right:
            res += calcs[i][k]
        elif l + real_blocksize[i] - 1 >= left:
            for idx in range(max(0, left - l), min(real_blocksize[i], right - l + 1)):
                if blocks[i][idx] == k:
                    res += 1
        l += real_blocksize[i]
    return res
last_ans = 0
query_cnt = 0
reconstruct()
q = II()
for _ in range(q):
    query = LII()
    for i in range(1, len(query)):
        query[i] = (query[i] + last_ans - 1) % n + 1
    if query[0] == 1:
        (l, r) = (query[1] - 1, query[2] - 1)
        if l > r:
            (l, r) = (r, l)
        query_cnt += 1
        if query_cnt == query_time:
            query_cnt = 0
            reconstruct()
        val = delete(r)
        insert(l, val)
    else:
        (l, r, k) = (query[1] - 1, query[2] - 1, query[3])
        if l > r:
            (l, r) = (r, l)
        last_ans = find(l, r, k)
        print(last_ans)

Solution (Python):
from typing import Sequence, List, Tuple
from heapq import heappush, heappop
from array import array

class WaveletMatrix:

    def __init__(self, sigma: int, a: Sequence[int]=[]):
        self.sigma: int = sigma
        self.log: int = (sigma - 1).bit_length()
        self.v: List[BitVector] = [None] * self.log
        self.mid: array[int] = array('I', bytes(4 * self.log))
        self.size: int = len(a)
        self._build(a)

    def _build(self, a: Sequence[int]) -> None:
        """"""
        for bit in range(self.log - 1, -1, -1):
            v = BitVector(self.size)
            (zero, one) = ([], [])
            for (i, e) in enumerate(a):
                if e >> bit & 1:
                    v.set(i)
                    one.append(e)
                else:
                    zero.append(e)
            v.build()
            self.mid[bit] = len(zero)
            self.v[bit] = v
            a = zero + one

    def access(self, k: int) -> int:
        """"""
        s = 0
        for bit in range(self.log - 1, -1, -1):
            if self.v[bit].access(k):
                s |= 1 << bit
                k = self.v[bit].rank1(k) + self.mid[bit]
            else:
                k = self.v[bit].rank0(k)
        return s

    def __getitem__(self, k: int) -> int:
        return self.access(k)

    def rank(self, r: int, x: int) -> int:
        """"""
        assert 0 <= r <= self.size, f'IndexError: r={r}, size={self.size}'
        assert 0 <= x <= self.sigma, f'ValueError'
        l = 0
        mid = self.mid
        for bit in range(self.log - 1, -1, -1):
            if x >> bit & 1:
                l = self.v[bit].rank1(l) + mid[bit]
                r = self.v[bit].rank1(r) + mid[bit]
            else:
                l = self.v[bit].rank0(l)
                r = self.v[bit].rank0(r)
        return r - l

    def select(self, k: int, x: int) -> int:
        """"""
        s = 0
        for bit in range(self.log - 1, -1, -1):
            if x >> bit & 1:
                s = self.v[bit].rank0(self.size) + self.v[bit].rank1(s)
            else:
                s = self.v[bit].rank0(s)
        s += k
        for bit in range(self.log):
            if x >> bit & 1:
                s = self.v[bit].select1(s - self.v[bit].rank0(self.size))
            else:
                s = self.v[bit].select0(s)
        return s

    def kth_smallest(self, l: int, r: int, k: int) -> int:
        """"""
        assert 0 <= l <= r <= self.size
        s = 0
        mid = self.mid
        for bit in range(self.log - 1, -1, -1):
            v = self.v[bit]
            (r0, l0) = (v.rank0(r), v.rank0(l))
            cnt = r0 - l0
            if cnt <= k:
                s |= 1 << bit
                k -= cnt
                l = l - l0 + mid[bit]
                r = r - r0 + mid[bit]
            else:
                l = l0
                r = r0
        return s
    quantile = kth_smallest

    def kth_largest(self, l: int, r: int, k: int) -> int:
        return self.kth_smallest(l, r, r - l - k - 1)

    def topk(self, l: int, r: int, k: int) -> List[Tuple[int, int]]:
        hq: List[Tuple[int, int, int, int]] = [(-(r - l), 0, l, self.log - 1)]
        ans = []
        while hq:
            (length, x, l, bit) = heappop(hq)
            length = -length
            if bit == -1:
                ans.append((x, length))
                k -= 1
                if k == 0:
                    break
            else:
                r = l + length
                l0 = self.v[bit].rank0(l)
                r0 = self.v[bit].rank0(r)
                if l0 < r0:
                    heappush(hq, (-(r0 - l0), x, l0, bit - 1))
                l1 = self.v[bit].rank1(l) + self.mid[bit]
                r1 = self.v[bit].rank1(r) + self.mid[bit]
                if l1 < r1:
                    heappush(hq, (-(r1 - l1), x | 1 << bit, l1, bit - 1))
        return ans

    def sum(self, l: int, r: int) -> int:
        assert False, f'Yabai Keisanryo Error'
        return sum((k * v for (k, v) in self.topk(l, r, r - l)))

    def _range_freq(self, l: int, r: int, x: int) -> int:
        """"""
        ans = 0
        for bit in range(self.log - 1, -1, -1):
            l0 = self.v[bit].rank0(l)
            r0 = self.v[bit].rank0(r)
            if x >> bit & 1:
                ans += r0 - l0
                l += self.mid[bit] - l0
                r += self.mid[bit] - r0
            else:
                l = l0
                r = r0
        return ans

    def range_freq(self, l: int, r: int, x: int, y: int) -> int:
        return self._range_freq(l, r, y) - self._range_freq(l, r, x)

    def prev_value(self, l: int, r: int, x: int) -> int:
        return self.kth_smallest(l, r, self._range_freq(l, r, x) - 1)

    def next_value(self, l: int, r: int, x: int) -> int:
        return self.kth_smallest(l, r, self._range_freq(l, r, x))

    def range_count(self, l: int, r: int, x: int) -> int:
        return self.rank(r, x) - self.rank(l, x)

    def __len__(self):
        return self.size

    def __str__(self):
        return f'WaveletMatrix{[self.access(i) for i in range(self.size)]}'
from array import array
from typing import Tuple, List, Sequence
from __pypy__ import newlist_hint

class AVLTreeBitVector:

    @staticmethod
    def _popcount(x: int) -> int:
        x = x - (x >> 1 & 1431655765)
        x = (x & 858993459) + (x >> 2 & 858993459)
        x = x + (x >> 4) & 252645135
        x += x >> 8
        x += x >> 16
        return x & 127

    def __init__(self, a: Sequence[int]):
        self.root = 0
        self.bit_len = array('B', bytes(1))
        self.key = array('I', bytes(4))
        self.size = array('I', bytes(4))
        self.total = array('I', bytes(4))
        self.left = array('I', bytes(4))
        self.right = array('I', bytes(4))
        self.balance = array('b', bytes(1))
        self.end = 1
        self.w = 32
        if a:
            self._build(a)

    def reserve(self, n: int) -> None:
        n = n // self.w + 1
        a = array('I', bytes(4 * n))
        self.bit_len += array('B', bytes(n))
        self.key += a
        self.size += a
        self.total += a
        self.left += a
        self.right += a
        self.balance += array('b', bytes(n))

    def _build(self, a: Sequence[int]) -> None:
        (key, bit_len, left, right, size, balance, total) = (self.key, self.bit_len, self.left, self.right, self.size, self.balance, self.total)
        _popcount = AVLTreeBitVector._popcount

        def rec(l: int, r: int) -> Tuple[int, int]:
            mid = l + r >> 1
            (hl, hr) = (0, 0)
            if l != mid:
                (left[mid], hl) = rec(l, mid)
                size[mid] += size[left[mid]]
                total[mid] += total[left[mid]]
            if mid + 1 != r:
                (right[mid], hr) = rec(mid + 1, r)
                size[mid] += size[right[mid]]
                total[mid] += total[right[mid]]
            balance[mid] = hl - hr
            return (mid, max(hl, hr) + 1)
        if not (hasattr(a, '__getitem__') and hasattr(a, '__len__')):
            a = list(a)
        n = len(a)
        end = self.end
        self.reserve(n)
        i = 0
        indx = end
        for i in range(0, n, self.w):
            j = 0
            v = 0
            while j < self.w and i + j < n:
                v <<= 1
                v |= a[i + j]
                j += 1
            key[indx] = v
            bit_len[indx] = j
            size[indx] = j
            total[indx] = _popcount(v)
            indx += 1
        self.end = indx
        self.root = rec(end, self.end)[0]

    def _rotate_L(self, node: int) -> int:
        (left, right, size, balance, total) = (self.left, self.right, self.size, self.balance, self.total)
        u = left[node]
        size[u] = size[node]
        total[u] = total[node]
        size[node] -= size[left[u]] + self.bit_len[u]
        total[node] -= total[left[u]] + AVLTreeBitVector._popcount(self.key[u])
        left[node] = right[u]
        right[u] = node
        if balance[u] == 1:
            balance[u] = 0
            balance[node] = 0
        else:
            balance[u] = -1
            balance[node] = 1
        return u

    def _rotate_R(self, node: int) -> int:
        (left, right, size, balance, total) = (self.left, self.right, self.size, self.balance, self.total)
        u = right[node]
        size[u] = size[node]
        total[u] = total[node]
        size[node] -= size[right[u]] + self.bit_len[u]
        total[node] -= total[right[u]] + AVLTreeBitVector._popcount(self.key[u])
        right[node] = left[u]
        left[u] = node
        if balance[u] == -1:
            balance[u] = 0
            balance[node] = 0
        else:
            balance[u] = 1
            balance[node] = -1
        return u

    def _update_balance(self, node: int) -> None:
        balance = self.balance
        if balance[node] == 1:
            balance[self.right[node]] = -1
            balance[self.left[node]] = 0
        elif balance[node] == -1:
            balance[self.right[node]] = 0
            balance[self.left[node]] = 1
        else:
            balance[self.right[node]] = 0
            balance[self.left[node]] = 0
        balance[node] = 0

    def _rotate_LR(self, node: int) -> int:
        (left, right, size, total) = (self.left, self.right, self.size, self.total)
        B = left[node]
        E = right[B]
        size[E] = size[node]
        size[node] -= size[B] - size[right[E]]
        size[B] -= size[right[E]] + self.bit_len[E]
        total[E] = total[node]
        total[node] -= total[B] - total[right[E]]
        total[B] -= total[right[E]] + AVLTreeBitVector._popcount(self.key[E])
        right[B] = left[E]
        left[E] = B
        left[node] = right[E]
        right[E] = node
        self._update_balance(E)
        return E

    def _rotate_RL(self, node: int) -> int:
        (left, right, size, total) = (self.left, self.right, self.size, self.total)
        C = right[node]
        D = left[C]
        size[D] = size[node]
        size[node] -= size[C] - size[left[D]]
        size[C] -= size[left[D]] + self.bit_len[D]
        total[D] = total[node]
        total[node] -= total[C] - total[left[D]]
        total[C] -= total[left[D]] + AVLTreeBitVector._popcount(self.key[D])
        left[C] = right[D]
        right[D] = C
        right[node] = left[D]
        left[D] = node
        self._update_balance(D)
        return D

    def _pref(self, r: int) -> int:
        (left, right, bit_len, size, key, total) = (self.left, self.right, self.bit_len, self.size, self.key, self.total)
        node = self.root
        s = 0
        while r > 0:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] < r <= t:
                r -= size[left[node]]
                s += total[left[node]] + AVLTreeBitVector._popcount(key[node] >> bit_len[node] - r)
                break
            if t > r:
                node = left[node]
            else:
                s += total[left[node]] + AVLTreeBitVector._popcount(key[node])
                node = right[node]
                r -= t
        return s

    def _make_node(self, key: int, bit_len: int) -> int:
        end = self.end
        if end >= len(self.key):
            self.key.append(key)
            self.bit_len.append(bit_len)
            self.size.append(bit_len)
            self.total.append(AVLTreeBitVector._popcount(key))
            self.left.append(0)
            self.right.append(0)
            self.balance.append(0)
        else:
            self.key[end] = key
            self.bit_len[end] = bit_len
            self.size[end] = bit_len
            self.total[end] = AVLTreeBitVector._popcount(key)
        self.end += 1
        return end

    def insert(self, k: int, key: int) -> None:
        if self.root == 0:
            self.root = self._make_node(key, 1)
            return
        (left, right, size, bit_len, balance, keys, total) = (self.left, self.right, self.size, self.bit_len, self.balance, self.key, self.total)
        node = self.root
        path = []
        d = 0
        while node:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k <= t:
                break
            d <<= 1
            size[node] += 1
            total[node] += key
            path.append(node)
            node = left[node] if t > k else right[node]
            if t > k:
                d |= 1
            else:
                k -= t
        k -= size[left[node]]
        if bit_len[node] < self.w:
            v = keys[node]
            bl = bit_len[node] - k
            keys[node] = (v >> bl << 1 | key) << bl | v & (1 << bl) - 1
            bit_len[node] += 1
            size[node] += 1
            total[node] += key
            return
        path.append(node)
        size[node] += 1
        total[node] += key
        v = keys[node]
        bl = self.w - k
        v = (v >> bl << 1 | key) << bl | v & (1 << bl) - 1
        left_key = v >> self.w
        left_key_popcount = left_key & 1
        keys[node] = v & (1 << self.w) - 1
        node = left[node]
        d <<= 1
        d |= 1
        if not node:
            if bit_len[path[-1]] < self.w:
                bit_len[path[-1]] += 1
                keys[path[-1]] = keys[path[-1]] << 1 | left_key
                return
            else:
                left[path[-1]] = self._make_node(left_key, 1)
        else:
            path.append(node)
            size[node] += 1
            total[node] += left_key_popcount
            d <<= 1
            while right[node]:
                node = right[node]
                path.append(node)
                size[node] += 1
                total[node] += left_key_popcount
                d <<= 1
            if bit_len[node] < self.w:
                bit_len[node] += 1
                keys[node] = keys[node] << 1 | left_key
                return
            else:
                right[node] = self._make_node(left_key, 1)
        new_node = 0
        while path:
            node = path.pop()
            balance[node] += 1 if d & 1 else -1
            d >>= 1
            if balance[node] == 0:
                break
            if balance[node] == 2:
                new_node = self._rotate_LR(node) if balance[left[node]] == -1 else self._rotate_L(node)
                break
            elif balance[node] == -2:
                new_node = self._rotate_RL(node) if balance[right[node]] == 1 else self._rotate_R(node)
                break
        if new_node:
            if path:
                if d & 1:
                    left[path[-1]] = new_node
                else:
                    right[path[-1]] = new_node
            else:
                self.root = new_node

    def _pop_under(self, path: List[int], d: int, node: int, res: int) -> None:
        (left, right, size, bit_len, balance, keys, total) = (self.left, self.right, self.size, self.bit_len, self.balance, self.key, self.total)
        (fd, lmax_total, lmax_bit_len) = (0, 0, 0)
        if left[node] and right[node]:
            path.append(node)
            d <<= 1
            d |= 1
            lmax = left[node]
            while right[lmax]:
                path.append(lmax)
                d <<= 1
                fd <<= 1
                fd |= 1
                lmax = right[lmax]
            lmax_total = AVLTreeBitVector._popcount(keys[lmax])
            lmax_bit_len = bit_len[lmax]
            keys[node] = keys[lmax]
            bit_len[node] = lmax_bit_len
            node = lmax
        cnode = right[node] if left[node] == 0 else left[node]
        if path:
            if d & 1:
                left[path[-1]] = cnode
            else:
                right[path[-1]] = cnode
        else:
            self.root = cnode
            return
        while path:
            new_node = 0
            node = path.pop()
            balance[node] -= 1 if d & 1 else -1
            size[node] -= lmax_bit_len if fd & 1 else 1
            total[node] -= lmax_total if fd & 1 else res
            d >>= 1
            fd >>= 1
            if balance[node] == 2:
                new_node = self._rotate_LR(node) if balance[left[node]] < 0 else self._rotate_L(node)
            elif balance[node] == -2:
                new_node = self._rotate_RL(node) if balance[right[node]] > 0 else self._rotate_R(node)
            elif balance[node] != 0:
                break
            if new_node:
                if not path:
                    self.root = new_node
                    return
                if d & 1:
                    left[path[-1]] = new_node
                else:
                    right[path[-1]] = new_node
                if balance[new_node] != 0:
                    break
        while path:
            node = path.pop()
            size[node] -= lmax_bit_len if fd & 1 else 1
            total[node] -= lmax_total if fd & 1 else res
            fd >>= 1

    def pop(self, k: int) -> int:
        assert 0 <= k < len(self)
        (left, right, size) = (self.left, self.right, self.size)
        (bit_len, balance, keys, total) = (self.bit_len, self.balance, self.key, self.total)
        node = self.root
        d = 0
        path = []
        while node:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k < t:
                break
            path.append(node)
            node = left[node] if t > k else right[node]
            d <<= 1
            if t > k:
                d |= 1
            else:
                k -= t
        k -= size[left[node]]
        v = keys[node]
        res = v >> bit_len[node] - k - 1 & 1
        if bit_len[node] == 1:
            self._pop_under(path, d, node, res)
            return res
        keys[node] = v >> bit_len[node] - k << bit_len[node] - k - 1 | v & (1 << bit_len[node] - k - 1) - 1
        bit_len[node] -= 1
        size[node] -= 1
        total[node] -= res
        for p in path:
            size[p] -= 1
            total[p] -= res
        return res

    def set(self, k: int, v: int) -> None:
        self.__setitem__(k, v)

    def tolist(self) -> List[int]:
        (left, right, key, bit_len) = (self.left, self.right, self.key, self.bit_len)
        a = newlist_hint(len(self))
        if not self.root:
            return a

        def rec(node):
            if left[node]:
                rec(left[node])
            for i in range(bit_len[node] - 1, -1, -1):
                a.append(key[node] >> i & 1)
            if right[node]:
                rec(right[node])
        rec(self.root)
        return a

    def debug(self) -> None:
        print(f'debug ##########')
        print(f'self.root={self.root!r}')
        print(f'len(self.key)={len(self.key)!r}')
        print(f'bit_length():', [bin(x).count('1') for x in self.key])
        print(f'self.key={self.key!r}')
        print(f'self.bit_len={self.bit_len!r}')
        print(f'self.size={self.size!r}')
        print(f'self.total={self.total!r}')
        print(f'self.balance={self.balance!r}')
        print(f'self.left={self.left!r}')
        print(f'self.right={self.right!r}')

    def debug_acc(self) -> None:
        (left, right) = (self.left, self.right)
        key = self.key

        def rec(node):
            acc = self._popcount(key[node])
            if left[node]:
                acc += rec(left[node])
            if right[node]:
                acc += rec(right[node])
            if acc != self.total[node]:
                assert False, 'acc Error'
            return acc
        rec(self.root)

    def debug_height(self) -> int:
        (left, right) = (self.left, self.right)
        h = 0

        def rec(node, dep):
            nonlocal h
            h = max(h, dep)
            if left[node]:
                rec(left[node], dep + 1)
            if right[node]:
                rec(right[node], dep + 1)
        rec(self.root, 0)
        return h

    def access(self, k: int) -> int:
        return self.__getitem__(k)

    def rank0(self, r: int) -> int:
        return r - self._pref(r)

    def rank1(self, r: int) -> int:
        return self._pref(r)

    def rank(self, r: int, v: int) -> int:
        return self.rank1(r) if v else self.rank0(r)

    def select0(self, k: int) -> int:
        if k < 0 or self.rank0(len(self)) <= k:
            return -1
        (l, r) = (0, len(self))
        while r - l > 1:
            m = l + r >> 1
            if m - self._pref(m) > k:
                r = m
            else:
                l = m
        return l

    def select1(self, k: int) -> int:
        if k < 0 or self.rank1(len(self)) <= k:
            return -1
        (l, r) = (0, len(self))
        while r - l > 1:
            m = l + r >> 1
            if self._pref(m) > k:
                r = m
            else:
                l = m
        return l

    def select(self, k: int, v: int) -> int:
        return self.select1(k) if v else self.select0(k)

    def _insert_and_rank1(self, k: int, key: int) -> int:
        if self.root == 0:
            self.root = self._make_node(key, 1)
            return 0
        (left, right, size, bit_len, balance, keys, total) = (self.left, self.right, self.size, self.bit_len, self.balance, self.key, self.total)
        node = self.root
        s = 0
        path = []
        d = 0
        while node:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k <= t:
                break
            if t <= k:
                s += total[left[node]] + AVLTreeBitVector._popcount(keys[node])
            d <<= 1
            size[node] += 1
            total[node] += key
            path.append(node)
            node = left[node] if t > k else right[node]
            if t > k:
                d |= 1
            else:
                k -= t
        k -= size[left[node]]
        s += total[left[node]] + AVLTreeBitVector._popcount(keys[node] >> bit_len[node] - k)
        if bit_len[node] < self.w:
            v = keys[node]
            bl = bit_len[node] - k
            keys[node] = (v >> bl << 1 | key) << bl | v & (1 << bl) - 1
            bit_len[node] += 1
            size[node] += 1
            total[node] += key
            return s
        path.append(node)
        size[node] += 1
        total[node] += key
        v = keys[node]
        bl = self.w - k
        v = (v >> bl << 1 | key) << bl | v & (1 << bl) - 1
        left_key = v >> self.w
        left_key_popcount = left_key & 1
        keys[node] = v & (1 << self.w) - 1
        node = left[node]
        d <<= 1
        d |= 1
        if not node:
            if bit_len[path[-1]] < self.w:
                bit_len[path[-1]] += 1
                keys[path[-1]] = keys[path[-1]] << 1 | left_key
                return s
            else:
                left[path[-1]] = self._make_node(left_key, 1)
        else:
            path.append(node)
            size[node] += 1
            total[node] += left_key_popcount
            d <<= 1
            while right[node]:
                node = right[node]
                path.append(node)
                size[node] += 1
                total[node] += left_key_popcount
                d <<= 1
            if bit_len[node] < self.w:
                bit_len[node] += 1
                keys[node] = keys[node] << 1 | left_key
                return s
            else:
                right[node] = self._make_node(left_key, 1)
        new_node = 0
        while path:
            node = path.pop()
            balance[node] += 1 if d & 1 else -1
            d >>= 1
            if balance[node] == 0:
                break
            if balance[node] == 2:
                new_node = self._rotate_LR(node) if balance[left[node]] == -1 else self._rotate_L(node)
                break
            elif balance[node] == -2:
                new_node = self._rotate_RL(node) if balance[right[node]] == 1 else self._rotate_R(node)
                break
        if new_node:
            if path:
                if d & 1:
                    left[path[-1]] = new_node
                else:
                    right[path[-1]] = new_node
            else:
                self.root = new_node
        return s

    def _access_pop_and_rank1(self, k: int) -> int:
        assert 0 <= k < len(self)
        (left, right, size) = (self.left, self.right, self.size)
        (bit_len, balance, keys, total) = (self.bit_len, self.balance, self.key, self.total)
        s = 0
        node = self.root
        d = 0
        path = []
        while node:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k < t:
                break
            if t <= k:
                s += total[left[node]] + AVLTreeBitVector._popcount(keys[node])
            path.append(node)
            node = left[node] if t > k else right[node]
            d <<= 1
            if t > k:
                d |= 1
            else:
                k -= t
        k -= size[left[node]]
        s += total[left[node]] + AVLTreeBitVector._popcount(keys[node] >> bit_len[node] - k)
        v = keys[node]
        res = v >> bit_len[node] - k - 1 & 1
        if bit_len[node] == 1:
            self._pop_under(path, d, node, res)
            return s << 1 | res
        keys[node] = v >> bit_len[node] - k << bit_len[node] - k - 1 | v & (1 << bit_len[node] - k - 1) - 1
        bit_len[node] -= 1
        size[node] -= 1
        total[node] -= res
        for p in path:
            size[p] -= 1
            total[p] -= res
        return s << 1 | res

    def __getitem__(self, k: int) -> int:
        assert 0 <= k < len(self)
        (left, right, bit_len, size, key) = (self.left, self.right, self.bit_len, self.size, self.key)
        node = self.root
        while True:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k < t:
                k -= size[left[node]]
                return key[node] >> bit_len[node] - k - 1 & 1
            elif t > k:
                node = left[node]
            else:
                node = right[node]
                k -= t

    def __setitem__(self, k: int, v: int):
        (left, right, bit_len, size, key) = (self.left, self.right, self.bit_len, self.size, self.key)
        node = self.root
        while True:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k < t:
                k -= size[left[node]]
                if v:
                    key[node] |= 1 << k
                else:
                    key[node] &= ~(1 << k)
                return
            elif t > k:
                node = left[node]
            else:
                node = right[node]
                k -= t

    def __str__(self):
        return str(self.tolist())

    def __len__(self):
        return self.size[self.root]

    def __repr__(self):
        return f'AVLTreeBitVector({self})'
from typing import Sequence, List
from array import array

class DynamicWaveletMatrix(WaveletMatrix):

    def __init__(self, sigma: int, a: Sequence[int]=[]):
        self.sigma: int = sigma
        self.log: int = (sigma - 1).bit_length()
        self.v: List[AVLTreeBitVector] = [None] * self.log
        self.mid: array[int] = array('I', bytes(4 * self.log))
        self.size: int = len(a)
        self._build(a)

    def _build(self, a: Sequence[int]) -> None:
        """"""
        v = array('B', bytes(self.size))
        for bit in range(self.log - 1, -1, -1):
            (zero, one) = ([], [])
            for (i, e) in enumerate(a):
                if e >> bit & 1:
                    v[i] = 1
                    one.append(e)
                else:
                    v[i] = 0
                    zero.append(e)
            self.mid[bit] = len(zero)
            self.v[bit] = AVLTreeBitVector(v)
            a = zero + one

    def reserve(self, n: int) -> None:
        for v in self.v:
            v.reserve(n)

    def insert(self, k: int, x: int) -> None:
        mid = self.mid
        for bit in range(self.log - 1, -1, -1):
            v = self.v[bit]
            if x >> bit & 1:
                s = v._insert_and_rank1(k, 1)
                k = s + mid[bit]
            else:
                s = v._insert_and_rank1(k, 0)
                k -= s
                mid[bit] += 1
        self.size += 1

    def pop(self, k: int) -> int:
        mid = self.mid
        ans = 0
        for bit in range(self.log - 1, -1, -1):
            v = self.v[bit]
            sb = v._access_pop_and_rank1(k)
            s = sb >> 1
            if sb & 1:
                ans |= 1 << bit
                k = s + mid[bit]
            else:
                mid[bit] -= 1
                k -= s
        self.size -= 1
        return ans

    def update(self, k: int, x: int) -> None:
        self.pop(k)
        self.insert(k, x)

    def __setitem__(self, k: int, x: int):
        self.update(k, x)

    def __str__(self):
        return f'DynamicWaveletMatrix({[self.access(i) for i in range(self.size)]})'
import os
from __pypy__.builders import StringBuilder

class FastO:
    sb = StringBuilder()

    @classmethod
    def write(cls, *args, sep: str=' ', end: str='\n', flush: bool=False) -> None:
        append = cls.sb.append
        for i in range(len(args) - 1):
            append(str(args[i]))
            append(sep)
        if args:
            append(str(args[-1]))
        append(end)
        if flush:
            cls.flush()

    @classmethod
    def flush(cls) -> None:
        os.write(1, cls.sb.build().encode())
        cls.sb = StringBuilder()
write = FastO.write
flush = FastO.flush
import sys
input = lambda : sys.stdin.buffer.readline().rstrip()
n = int(input())
A = list(map(int, input().split()))
q = int(input())
wm = DynamicWaveletMatrix(10 ** 5, A)
ans = 0
for _ in range(q):
    (com, *qu) = map(int, input().split())
    if com == 1:
        (l, r) = qu
        l = (l + ans - 1) % n
        r = (r + ans - 1) % n
        if l > r:
            (l, r) = (r, l)
        x = wm.pop(r)
        wm.insert(l, x)
    else:
        (l, r, k) = qu
        l = (l + ans - 1) % n
        r = (r + ans - 1) % n
        if l > r:
            (l, r) = (r, l)
        k = (k + ans - 1) % n + 1
        ans = wm.range_count(l, r + 1, k)
        write(ans)
flush()

Solution (Python):
from array import array
from typing import Tuple, List, Iterable, Sequence
from __pypy__ import newlist_hint

class AVLTreeBitVector:

    @staticmethod
    def _popcount(x: int) -> int:
        x = x - (x >> 1 & 1431655765)
        x = (x & 858993459) + (x >> 2 & 858993459)
        x = x + (x >> 4) & 252645135
        x += x >> 8
        x += x >> 16
        return x & 127

    def __init__(self, a: Sequence[int]):
        self.root = 0
        self.bit_len = array('B', bytes(1))
        self.key = array('I', bytes(4))
        self.size = array('I', bytes(4))
        self.total = array('I', bytes(4))
        self.left = array('I', bytes(4))
        self.right = array('I', bytes(4))
        self.balance = array('b', bytes(1))
        self.end = 1
        self.w = 32
        if a:
            self._build(a)

    def reserve(self, n: int) -> None:
        n = n // self.w + 1
        a = array('I', bytes(4 * n))
        self.bit_len += array('B', bytes(n))
        self.key += a
        self.size += a
        self.total += a
        self.left += a
        self.right += a
        self.balance += array('b', bytes(n))

    def _build(self, a: Sequence[int]) -> None:
        (key, bit_len, left, right, size, balance, total) = (self.key, self.bit_len, self.left, self.right, self.size, self.balance, self.total)
        _popcount = AVLTreeBitVector._popcount

        def rec(l: int, r: int) -> Tuple[int, int]:
            mid = l + r >> 1
            (hl, hr) = (0, 0)
            if l != mid:
                (left[mid], hl) = rec(l, mid)
                size[mid] += size[left[mid]]
                total[mid] += total[left[mid]]
            if mid + 1 != r:
                (right[mid], hr) = rec(mid + 1, r)
                size[mid] += size[right[mid]]
                total[mid] += total[right[mid]]
            balance[mid] = hl - hr
            return (mid, max(hl, hr) + 1)
        if not (hasattr(a, '__getitem__') and hasattr(a, '__len__')):
            a = list(a)
        n = len(a)
        end = self.end
        self.reserve(n)
        i = 0
        indx = end
        for i in range(0, n, self.w):
            j = 0
            v = 0
            while j < self.w and i + j < n:
                v <<= 1
                v |= a[i + j]
                j += 1
            key[indx] = v
            bit_len[indx] = j
            size[indx] = j
            total[indx] = _popcount(v)
            indx += 1
        self.end = indx
        self.root = rec(end, self.end)[0]

    def _rotate_L(self, node: int) -> int:
        (left, right, size, balance, total) = (self.left, self.right, self.size, self.balance, self.total)
        u = left[node]
        size[u] = size[node]
        total[u] = total[node]
        size[node] -= size[left[u]] + self.bit_len[u]
        total[node] -= total[left[u]] + AVLTreeBitVector._popcount(self.key[u])
        left[node] = right[u]
        right[u] = node
        if balance[u] == 1:
            balance[u] = 0
            balance[node] = 0
        else:
            balance[u] = -1
            balance[node] = 1
        return u

    def _rotate_R(self, node: int) -> int:
        (left, right, size, balance, total) = (self.left, self.right, self.size, self.balance, self.total)
        u = right[node]
        size[u] = size[node]
        total[u] = total[node]
        size[node] -= size[right[u]] + self.bit_len[u]
        total[node] -= total[right[u]] + AVLTreeBitVector._popcount(self.key[u])
        right[node] = left[u]
        left[u] = node
        if balance[u] == -1:
            balance[u] = 0
            balance[node] = 0
        else:
            balance[u] = 1
            balance[node] = -1
        return u

    def _update_balance(self, node: int) -> None:
        balance = self.balance
        if balance[node] == 1:
            balance[self.right[node]] = -1
            balance[self.left[node]] = 0
        elif balance[node] == -1:
            balance[self.right[node]] = 0
            balance[self.left[node]] = 1
        else:
            balance[self.right[node]] = 0
            balance[self.left[node]] = 0
        balance[node] = 0

    def _rotate_LR(self, node: int) -> int:
        (left, right, size, total) = (self.left, self.right, self.size, self.total)
        B = left[node]
        E = right[B]
        size[E] = size[node]
        size[node] -= size[B] - size[right[E]]
        size[B] -= size[right[E]] + self.bit_len[E]
        total[E] = total[node]
        total[node] -= total[B] - total[right[E]]
        total[B] -= total[right[E]] + AVLTreeBitVector._popcount(self.key[E])
        right[B] = left[E]
        left[E] = B
        left[node] = right[E]
        right[E] = node
        self._update_balance(E)
        return E

    def _rotate_RL(self, node: int) -> int:
        (left, right, size, total) = (self.left, self.right, self.size, self.total)
        C = right[node]
        D = left[C]
        size[D] = size[node]
        size[node] -= size[C] - size[left[D]]
        size[C] -= size[left[D]] + self.bit_len[D]
        total[D] = total[node]
        total[node] -= total[C] - total[left[D]]
        total[C] -= total[left[D]] + AVLTreeBitVector._popcount(self.key[D])
        left[C] = right[D]
        right[D] = C
        right[node] = left[D]
        left[D] = node
        self._update_balance(D)
        return D

    def _pref(self, r: int) -> int:
        (left, right, bit_len, size, key, total) = (self.left, self.right, self.bit_len, self.size, self.key, self.total)
        node = self.root
        s = 0
        while r > 0:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] < r <= t:
                r -= size[left[node]]
                s += total[left[node]] + AVLTreeBitVector._popcount(key[node] >> bit_len[node] - r)
                break
            if t > r:
                node = left[node]
            else:
                s += total[left[node]] + AVLTreeBitVector._popcount(key[node])
                node = right[node]
                r -= t
        return s

    def _make_node(self, key: int, bit_len: int) -> int:
        end = self.end
        if end >= len(self.key):
            self.key.append(key)
            self.bit_len.append(bit_len)
            self.size.append(bit_len)
            self.total.append(AVLTreeBitVector._popcount(key))
            self.left.append(0)
            self.right.append(0)
            self.balance.append(0)
        else:
            self.key[end] = key
            self.bit_len[end] = bit_len
            self.size[end] = bit_len
            self.total[end] = AVLTreeBitVector._popcount(key)
        self.end += 1
        return end

    def insert(self, k: int, key: int) -> None:
        if self.root == 0:
            self.root = self._make_node(key, 1)
            return
        (left, right, size, bit_len, balance, keys, total) = (self.left, self.right, self.size, self.bit_len, self.balance, self.key, self.total)
        node = self.root
        path = []
        d = 0
        while node:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k <= t:
                break
            d <<= 1
            size[node] += 1
            total[node] += key
            path.append(node)
            node = left[node] if t > k else right[node]
            if t > k:
                d |= 1
            else:
                k -= t
        k -= size[left[node]]
        if bit_len[node] < self.w:
            v = keys[node]
            bl = bit_len[node] - k
            keys[node] = (v >> bl << 1 | key) << bl | v & (1 << bl) - 1
            bit_len[node] += 1
            size[node] += 1
            total[node] += key
            return
        path.append(node)
        size[node] += 1
        total[node] += key
        v = keys[node]
        bl = self.w - k
        v = (v >> bl << 1 | key) << bl | v & (1 << bl) - 1
        left_key = v >> self.w
        left_key_popcount = left_key & 1
        keys[node] = v & (1 << self.w) - 1
        node = left[node]
        d <<= 1
        d |= 1
        if not node:
            if bit_len[path[-1]] < self.w:
                bit_len[path[-1]] += 1
                keys[path[-1]] = keys[path[-1]] << 1 | left_key
                return
            else:
                left[path[-1]] = self._make_node(left_key, 1)
        else:
            path.append(node)
            size[node] += 1
            total[node] += left_key_popcount
            d <<= 1
            while right[node]:
                node = right[node]
                path.append(node)
                size[node] += 1
                total[node] += left_key_popcount
                d <<= 1
            if bit_len[node] < self.w:
                bit_len[node] += 1
                keys[node] = keys[node] << 1 | left_key
                return
            else:
                right[node] = self._make_node(left_key, 1)
        new_node = 0
        while path:
            node = path.pop()
            balance[node] += 1 if d & 1 else -1
            d >>= 1
            if balance[node] == 0:
                break
            if balance[node] == 2:
                new_node = self._rotate_LR(node) if balance[left[node]] == -1 else self._rotate_L(node)
                break
            elif balance[node] == -2:
                new_node = self._rotate_RL(node) if balance[right[node]] == 1 else self._rotate_R(node)
                break
        if new_node:
            if path:
                if d & 1:
                    left[path[-1]] = new_node
                else:
                    right[path[-1]] = new_node
            else:
                self.root = new_node

    def _pop_under(self, path: List[int], d: int, node: int, res: int) -> None:
        (left, right, size, bit_len, balance, keys, total) = (self.left, self.right, self.size, self.bit_len, self.balance, self.key, self.total)
        (fd, lmax_total, lmax_bit_len) = (0, 0, 0)
        if left[node] and right[node]:
            path.append(node)
            d <<= 1
            d |= 1
            lmax = left[node]
            while right[lmax]:
                path.append(lmax)
                d <<= 1
                fd <<= 1
                fd |= 1
                lmax = right[lmax]
            lmax_total = AVLTreeBitVector._popcount(keys[lmax])
            lmax_bit_len = bit_len[lmax]
            keys[node] = keys[lmax]
            bit_len[node] = lmax_bit_len
            node = lmax
        cnode = right[node] if left[node] == 0 else left[node]
        if path:
            if d & 1:
                left[path[-1]] = cnode
            else:
                right[path[-1]] = cnode
        else:
            self.root = cnode
            return
        while path:
            new_node = 0
            node = path.pop()
            balance[node] -= 1 if d & 1 else -1
            size[node] -= lmax_bit_len if fd & 1 else 1
            total[node] -= lmax_total if fd & 1 else res
            d >>= 1
            fd >>= 1
            if balance[node] == 2:
                new_node = self._rotate_LR(node) if balance[left[node]] < 0 else self._rotate_L(node)
            elif balance[node] == -2:
                new_node = self._rotate_RL(node) if balance[right[node]] > 0 else self._rotate_R(node)
            elif balance[node] != 0:
                break
            if new_node:
                if not path:
                    self.root = new_node
                    return
                if d & 1:
                    left[path[-1]] = new_node
                else:
                    right[path[-1]] = new_node
                if balance[new_node] != 0:
                    break
        while path:
            node = path.pop()
            size[node] -= lmax_bit_len if fd & 1 else 1
            total[node] -= lmax_total if fd & 1 else res
            fd >>= 1

    def pop(self, k: int) -> int:
        assert 0 <= k < len(self)
        (left, right, size) = (self.left, self.right, self.size)
        (bit_len, balance, keys, total) = (self.bit_len, self.balance, self.key, self.total)
        node = self.root
        d = 0
        path = []
        while node:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k < t:
                break
            path.append(node)
            node = left[node] if t > k else right[node]
            d <<= 1
            if t > k:
                d |= 1
            else:
                k -= t
        k -= size[left[node]]
        v = keys[node]
        res = v >> bit_len[node] - k - 1 & 1
        if bit_len[node] == 1:
            self._pop_under(path, d, node, res)
            return res
        keys[node] = v >> bit_len[node] - k << bit_len[node] - k - 1 | v & (1 << bit_len[node] - k - 1) - 1
        bit_len[node] -= 1
        size[node] -= 1
        total[node] -= res
        for p in path:
            size[p] -= 1
            total[p] -= res
        return res

    def set(self, k: int, v: int) -> None:
        self.__setitem__(k, v)

    def tolist(self) -> List[int]:
        (left, right, key, bit_len) = (self.left, self.right, self.key, self.bit_len)
        a = newlist_hint(len(self))
        if not self.root:
            return a

        def rec(node):
            if left[node]:
                rec(left[node])
            for i in range(bit_len[node] - 1, -1, -1):
                a.append(key[node] >> i & 1)
            if right[node]:
                rec(right[node])
        rec(self.root)
        return a

    def debug(self) -> None:
        print(f'debug ##########')
        print(f'self.root={self.root!r}')
        print(f'len(self.key)={len(self.key)!r}')
        print(f'bit_length():', [bin(x).count('1') for x in self.key])
        print(f'self.key={self.key!r}')
        print(f'self.bit_len={self.bit_len!r}')
        print(f'self.size={self.size!r}')
        print(f'self.total={self.total!r}')
        print(f'self.balance={self.balance!r}')
        print(f'self.left={self.left!r}')
        print(f'self.right={self.right!r}')

    def debug_acc(self) -> None:
        (left, right) = (self.left, self.right)
        key = self.key

        def rec(node):
            acc = self._popcount(key[node])
            if left[node]:
                acc += rec(left[node])
            if right[node]:
                acc += rec(right[node])
            if acc != self.total[node]:
                assert False, 'acc Error'
            return acc
        rec(self.root)

    def debug_height(self) -> int:
        (left, right) = (self.left, self.right)
        h = 0

        def rec(node, dep):
            nonlocal h
            h = max(h, dep)
            if left[node]:
                rec(left[node], dep + 1)
            if right[node]:
                rec(right[node], dep + 1)
        rec(self.root, 0)
        return h

    def access(self, k: int) -> int:
        return self.__getitem__(k)

    def rank0(self, r: int) -> int:
        return r - self._pref(r)

    def rank1(self, r: int) -> int:
        return self._pref(r)

    def rank(self, r: int, v: int) -> int:
        return self.rank1(r) if v else self.rank0(r)

    def select0(self, k: int) -> int:
        if k < 0 or self.rank0(len(self)) <= k:
            return -1
        (l, r) = (0, len(self))
        while r - l > 1:
            m = l + r >> 1
            if m - self._pref(m) > k:
                r = m
            else:
                l = m
        return l

    def select1(self, k: int) -> int:
        if k < 0 or self.rank1(len(self)) <= k:
            return -1
        (l, r) = (0, len(self))
        while r - l > 1:
            m = l + r >> 1
            if self._pref(m) > k:
                r = m
            else:
                l = m
        return l

    def select(self, k: int, v: int) -> int:
        return self.select1(k) if v else self.select0(k)

    def _insert_and_rank1(self, k: int, key: int) -> int:
        if self.root == 0:
            self.root = self._make_node(key, 1)
            return 0
        (left, right, size, bit_len, balance, keys, total) = (self.left, self.right, self.size, self.bit_len, self.balance, self.key, self.total)
        node = self.root
        s = 0
        path = []
        d = 0
        while node:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k <= t:
                break
            if t <= k:
                s += total[left[node]] + AVLTreeBitVector._popcount(keys[node])
            d <<= 1
            size[node] += 1
            total[node] += key
            path.append(node)
            node = left[node] if t > k else right[node]
            if t > k:
                d |= 1
            else:
                k -= t
        k -= size[left[node]]
        s += total[left[node]] + AVLTreeBitVector._popcount(keys[node] >> bit_len[node] - k)
        if bit_len[node] < self.w:
            v = keys[node]
            bl = bit_len[node] - k
            keys[node] = (v >> bl << 1 | key) << bl | v & (1 << bl) - 1
            bit_len[node] += 1
            size[node] += 1
            total[node] += key
            return s
        path.append(node)
        size[node] += 1
        total[node] += key
        v = keys[node]
        bl = self.w - k
        v = (v >> bl << 1 | key) << bl | v & (1 << bl) - 1
        left_key = v >> self.w
        left_key_popcount = left_key & 1
        keys[node] = v & (1 << self.w) - 1
        node = left[node]
        d <<= 1
        d |= 1
        if not node:
            if bit_len[path[-1]] < self.w:
                bit_len[path[-1]] += 1
                keys[path[-1]] = keys[path[-1]] << 1 | left_key
                return s
            else:
                left[path[-1]] = self._make_node(left_key, 1)
        else:
            path.append(node)
            size[node] += 1
            total[node] += left_key_popcount
            d <<= 1
            while right[node]:
                node = right[node]
                path.append(node)
                size[node] += 1
                total[node] += left_key_popcount
                d <<= 1
            if bit_len[node] < self.w:
                bit_len[node] += 1
                keys[node] = keys[node] << 1 | left_key
                return s
            else:
                right[node] = self._make_node(left_key, 1)
        new_node = 0
        while path:
            node = path.pop()
            balance[node] += 1 if d & 1 else -1
            d >>= 1
            if balance[node] == 0:
                break
            if balance[node] == 2:
                new_node = self._rotate_LR(node) if balance[left[node]] == -1 else self._rotate_L(node)
                break
            elif balance[node] == -2:
                new_node = self._rotate_RL(node) if balance[right[node]] == 1 else self._rotate_R(node)
                break
        if new_node:
            if path:
                if d & 1:
                    left[path[-1]] = new_node
                else:
                    right[path[-1]] = new_node
            else:
                self.root = new_node
        return s

    def _access_pop_and_rank1(self, k: int) -> int:
        assert 0 <= k < len(self)
        (left, right, size) = (self.left, self.right, self.size)
        (bit_len, balance, keys, total) = (self.bit_len, self.balance, self.key, self.total)
        s = 0
        node = self.root
        d = 0
        path = []
        while node:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k < t:
                break
            if t <= k:
                s += total[left[node]] + AVLTreeBitVector._popcount(keys[node])
            path.append(node)
            node = left[node] if t > k else right[node]
            d <<= 1
            if t > k:
                d |= 1
            else:
                k -= t
        k -= size[left[node]]
        s += total[left[node]] + AVLTreeBitVector._popcount(keys[node] >> bit_len[node] - k)
        v = keys[node]
        res = v >> bit_len[node] - k - 1 & 1
        if bit_len[node] == 1:
            self._pop_under(path, d, node, res)
            return s << 1 | res
        keys[node] = v >> bit_len[node] - k << bit_len[node] - k - 1 | v & (1 << bit_len[node] - k - 1) - 1
        bit_len[node] -= 1
        size[node] -= 1
        total[node] -= res
        for p in path:
            size[p] -= 1
            total[p] -= res
        return s << 1 | res

    def __getitem__(self, k: int) -> int:
        assert 0 <= k < len(self)
        (left, right, bit_len, size, key) = (self.left, self.right, self.bit_len, self.size, self.key)
        node = self.root
        while True:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k < t:
                k -= size[left[node]]
                return key[node] >> bit_len[node] - k - 1 & 1
            elif t > k:
                node = left[node]
            else:
                node = right[node]
                k -= t

    def __setitem__(self, k: int, v: int):
        (left, right, bit_len, size, key) = (self.left, self.right, self.bit_len, self.size, self.key)
        node = self.root
        while True:
            t = size[left[node]] + bit_len[node]
            if t - bit_len[node] <= k < t:
                k -= size[left[node]]
                if v:
                    key[node] |= 1 << k
                else:
                    key[node] &= ~(1 << k)
                return
            elif t > k:
                node = left[node]
            else:
                node = right[node]
                k -= t

    def __str__(self):
        return str(self.tolist())

    def __len__(self):
        return self.size[self.root]

    def __repr__(self):
        return f'AVLTreeBitVector({self})'
from typing import Sequence, List, Tuple
from heapq import heappush, heappop
from array import array

class WaveletMatrix:

    def __init__(self, sigma: int, a: Sequence[int]=[]):
        self.sigma: int = sigma
        self.log: int = (sigma - 1).bit_length()
        self.v: List[BitVector] = [None] * self.log
        self.mid: array[int] = array('I', bytes(4 * self.log))
        self.size: int = len(a)
        self._build(a)

    def _build(self, a: Sequence[int]) -> None:
        """"""
        for bit in range(self.log - 1, -1, -1):
            v = BitVector(self.size)
            (zero, one) = ([], [])
            for (i, e) in enumerate(a):
                if e >> bit & 1:
                    v.set(i)
                    one.append(e)
                else:
                    zero.append(e)
            v.build()
            self.mid[bit] = len(zero)
            self.v[bit] = v
            a = zero + one

    def access(self, k: int) -> int:
        """"""
        s = 0
        for bit in range(self.log - 1, -1, -1):
            if self.v[bit].access(k):
                s |= 1 << bit
                k = self.v[bit].rank1(k) + self.mid[bit]
            else:
                k = self.v[bit].rank0(k)
        return s

    def __getitem__(self, k: int) -> int:
        return self.access(k)

    def rank(self, r: int, x: int) -> int:
        """"""
        assert 0 <= r <= self.size, f'IndexError: r={r}, size={self.size}'
        assert 0 <= x <= self.sigma, f'ValueError'
        l = 0
        mid = self.mid
        for bit in range(self.log - 1, -1, -1):
            if x >> bit & 1:
                l = self.v[bit].rank1(l) + mid[bit]
                r = self.v[bit].rank1(r) + mid[bit]
            else:
                l = self.v[bit].rank0(l)
                r = self.v[bit].rank0(r)
        return r - l

    def select(self, k: int, x: int) -> int:
        """"""
        s = 0
        for bit in range(self.log - 1, -1, -1):
            if x >> bit & 1:
                s = self.v[bit].rank0(self.size) + self.v[bit].rank1(s)
            else:
                s = self.v[bit].rank0(s)
        s += k
        for bit in range(self.log):
            if x >> bit & 1:
                s = self.v[bit].select1(s - self.v[bit].rank0(self.size))
            else:
                s = self.v[bit].select0(s)
        return s

    def kth_smallest(self, l: int, r: int, k: int) -> int:
        """"""
        assert 0 <= l <= r <= self.size
        s = 0
        mid = self.mid
        for bit in range(self.log - 1, -1, -1):
            v = self.v[bit]
            (r0, l0) = (v.rank0(r), v.rank0(l))
            cnt = r0 - l0
            if cnt <= k:
                s |= 1 << bit
                k -= cnt
                l = l - l0 + mid[bit]
                r = r - r0 + mid[bit]
            else:
                l = l0
                r = r0
        return s
    quantile = kth_smallest

    def kth_largest(self, l: int, r: int, k: int) -> int:
        return self.kth_smallest(l, r, r - l - k - 1)

    def topk(self, l: int, r: int, k: int) -> List[Tuple[int, int]]:
        hq: List[Tuple[int, int, int, int]] = [(-(r - l), 0, l, self.log - 1)]
        ans = []
        while hq:
            (length, x, l, bit) = heappop(hq)
            length = -length
            if bit == -1:
                ans.append((x, length))
                k -= 1
                if k == 0:
                    break
            else:
                r = l + length
                l0 = self.v[bit].rank0(l)
                r0 = self.v[bit].rank0(r)
                if l0 < r0:
                    heappush(hq, (-(r0 - l0), x, l0, bit - 1))
                l1 = self.v[bit].rank1(l) + self.mid[bit]
                r1 = self.v[bit].rank1(r) + self.mid[bit]
                if l1 < r1:
                    heappush(hq, (-(r1 - l1), x | 1 << bit, l1, bit - 1))
        return ans

    def sum(self, l: int, r: int) -> int:
        assert False, f'Yabai Keisanryo Error'
        return sum((k * v for (k, v) in self.topk(l, r, r - l)))

    def _range_freq(self, l: int, r: int, x: int) -> int:
        """"""
        ans = 0
        for bit in range(self.log - 1, -1, -1):
            l0 = self.v[bit].rank0(l)
            r0 = self.v[bit].rank0(r)
            if x >> bit & 1:
                ans += r0 - l0
                l += self.mid[bit] - l0
                r += self.mid[bit] - r0
            else:
                l = l0
                r = r0
        return ans

    def range_freq(self, l: int, r: int, x: int, y: int) -> int:
        return self._range_freq(l, r, y) - self._range_freq(l, r, x)

    def prev_value(self, l: int, r: int, x: int) -> int:
        return self.kth_smallest(l, r, self._range_freq(l, r, x) - 1)

    def next_value(self, l: int, r: int, x: int) -> int:
        return self.kth_smallest(l, r, self._range_freq(l, r, x))

    def range_count(self, l: int, r: int, x: int) -> int:
        return self.rank(r, x) - self.rank(l, x)

    def __len__(self):
        return self.size

    def __str__(self):
        return f'WaveletMatrix{[self.access(i) for i in range(self.size)]}'
from typing import Sequence, List
from array import array

class DynamicWaveletMatrix(WaveletMatrix):

    def __init__(self, sigma: int, a: Sequence[int]=[]):
        self.sigma: int = sigma
        self.log: int = (sigma - 1).bit_length()
        self.v: List[AVLTreeBitVector] = [None] * self.log
        self.mid: array[int] = array('I', bytes(4 * self.log))
        self.size: int = len(a)
        self._build(a)

    def _build(self, a: Sequence[int]) -> None:
        """"""
        v = array('B', bytes(self.size))
        for bit in range(self.log - 1, -1, -1):
            (zero, one) = ([], [])
            for (i, e) in enumerate(a):
                if e >> bit & 1:
                    v[i] = 1
                    one.append(e)
                else:
                    v[i] = 0
                    zero.append(e)
            self.mid[bit] = len(zero)
            self.v[bit] = AVLTreeBitVector(v)
            a = zero + one

    def reserve(self, n: int) -> None:
        for v in self.v:
            v.reserve(n)

    def insert(self, k: int, x: int) -> None:
        mid = self.mid
        for bit in range(self.log - 1, -1, -1):
            v = self.v[bit]
            if x >> bit & 1:
                s = v._insert_and_rank1(k, 1)
                k = s + mid[bit]
            else:
                s = v._insert_and_rank1(k, 0)
                k -= s
                mid[bit] += 1
        self.size += 1

    def pop(self, k: int) -> int:
        mid = self.mid
        ans = 0
        for bit in range(self.log - 1, -1, -1):
            v = self.v[bit]
            sb = v._access_pop_and_rank1(k)
            s = sb >> 1
            if sb & 1:
                ans |= 1 << bit
                k = s + mid[bit]
            else:
                mid[bit] -= 1
                k -= s
        self.size -= 1
        return ans

    def update(self, k: int, x: int) -> None:
        self.pop(k)
        self.insert(k, x)

    def __setitem__(self, k: int, x: int):
        self.update(k, x)

    def __str__(self):
        return f'DynamicWaveletMatrix({[self.access(i) for i in range(self.size)]})'
import os
from __pypy__.builders import StringBuilder

class FastO:
    sb = StringBuilder()

    @classmethod
    def write(cls, *args, sep: str=' ', end: str='\n', flush: bool=False) -> None:
        append = cls.sb.append
        for i in range(len(args) - 1):
            append(str(args[i]))
            append(sep)
        if args:
            append(str(args[-1]))
        append(end)
        if flush:
            cls.flush()

    @classmethod
    def flush(cls) -> None:
        os.write(1, cls.sb.build().encode())
        cls.sb = StringBuilder()
write = FastO.write
flush = FastO.flush
import sys
input = lambda : sys.stdin.buffer.readline().rstrip()
n = int(input())
A = list(map(int, input().split()))
q = int(input())
wm = DynamicWaveletMatrix(10 ** 5, A)
ans = 0
for _ in range(q):
    (com, *qu) = map(int, input().split())
    if com == 1:
        (l, r) = qu
        l = (l + ans - 1) % n
        r = (r + ans - 1) % n
        if l > r:
            (l, r) = (r, l)
        x = wm.pop(r)
        wm.insert(l, x)
    else:
        (l, r, k) = qu
        l = (l + ans - 1) % n
        r = (r + ans - 1) % n
        if l > r:
            (l, r) = (r, l)
        k = (k + ans - 1) % n + 1
        ans = wm.range_count(l, r + 1, k)
        write(ans)
flush()