You can't eat two apples of the same beauty value.

Is there a way to eat apples of all kinds of beauty values that appearred?

First of all, since the beauty values of the apples you eat are in strictly increasing order, any two of them have different beauty values.

So, for each beauty value, you can eat at most one apple.

In fact, it can be shown that it is always possible to eat exactly one apple of each beauty value. Let's say all the distinct beauty values are $$$v_1,v_2,\ldots,v_k\ (v_1\lt v_2\lt\ldots\lt v_k)$$$. You can eat one apple of beauty value $$$v_i$$$ during the $$$i$$$-th time you move along the full circle.

Therefore, the answer is the number of distinct numbers in beauty values. The time complexity is $$$\mathcal{O}(n)$$$.

#include <bits/stdc++.h>
using namespace std;
 
int t, n;
 
int main() {
    cin >> t;
 
    while (t--) {
        cin >> n;
        
        set<int> st;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            st.insert(x);
        }
 
        cout << (int) st.size() << '\n';
    }
 
    return 0;
}

import sys
input = lambda: sys.stdin.readline().strip()

t = int(input())
outs = []
 
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    # There can be hash collisions, but n is small enough.
    outs.append(len(set(nums)))
 
print('\n'.join(map(str, outs)))

Consider each bit of the numbers separately.

Different bits don't interfere with one another when you do bitwise operations. So, for each bit $$$k$$$, we can iterate over $$$2^3$$$ possibilities of $$$a_k = \mathtt{0} \text{ or } \mathtt{1}$$$, $$$b_k = \mathtt{0} \text{ or } \mathtt{1}$$$, and $$$c_k = \mathtt{0} \text{ or } \mathtt{1}$$$, and check whether it is consistent with the given numbers.

The time complexity for each test case is $$$\mathcal{O}(\log \max(x, y, z))$$$.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int MAXL = 60;
 
int t;
ll x, y, z;
 
int main() {
    cin >> t;
    while (t--) {
        cin >> x >> y >> z;
        ll a = 0, b = 0, c = 0;
        bool ans = true;
        for (int l = MAXL - 1; l >= 0; l--) {
            ll bit_x = x >> l & 1, bit_y = y >> l & 1, bit_z = z >> l & 1;
            bool found = false;
            for (ll bit_a : {0, 1}) {
                for (ll bit_b : {0, 1}) {
                    for (ll bit_c : {0, 1}) {
                        if ((bit_a & bit_b) == bit_x &&
                            (bit_b & bit_c) == bit_y &&
                            (bit_a & bit_c) == bit_z) {
                            found = true;
                            a |= bit_a << l;
                            b |= bit_b << l;
                            c |= bit_c << l;
                            break;
                        }
                    }
                    if (found) {
                        break;
                    }
                }
                if (found) {
                    break;
                }
            }
            if (!found) {
                ans = false;
                break;
            }
        }
        if (!ans) {
            cout << "NO\n";
        } else {
            assert((a & b) == x);
            assert((b & c) == y);
            assert((a & c) == z);
            cout << "YES\n";
        }
    }
    return 0;
}

import sys
input = lambda: sys.stdin.readline().strip()

t = int(input())
outs = []
 
for _ in range(t):
    x, y, z = map(int, input().split())
    
    a = x | z
    b = x | y
    c = y | z
    
    outs.append('YES' if a & b == x and b & c == y and a & c == z else 'NO')
 
print('\n'.join(outs))

You just need to check whether $$$(a,b,c)=(x|z,x|y,y|z)$$$ is a valid solution, where $$$|$$$ denotes the bitwise OR operation. Why?

Consider the line of symmetry. It intersects with the polygon at no more than $$$2$$$ sticks if we don't consider the endpoints of the sides.

Other sticks come in pairs.

Any line intersects with the polygon at no more than $$$2$$$ sticks (Here, we don't consider the endpoints of the sides when talking about intersection).

Consider the line of symmetry. The sticks not intersecting with it come in pairs of the same length.

Once we group the sticks in pairs of the same length (some sticks are not grouped), we should always use all of the pairs to construct the symmetrical convex polygon.

That is because, if we do not use all the pairs, for each unchosen pair, we can always add a copy of the stick on each side of the line of symmetry, which enlarges the perimeter. And if there exists a pair which we only use one of them as a side, it has to intersects with the line of symmetry. We can replace it with the pair on both sides of the line of symmetry and make the polygon convex with a larger perimeter.

Case 1: The line of symmetry intersects none of the sticks.

Only pairs of sticks with same length can be used. To obtain the largest perimeter, it is the most optimal to use all possible pairs.

Case 2: The line of symmetry intersects exactly one stick.

Let us call the stick that intersects the line of symmetry the odd stick. As long as the length of the odd stick is less than the total length of the pairs of sticks with identical length, we can use the odd stick. Hence, we can iterate through all possible sticks and check whether it is possible for it to be the odd stick in $$$O(1)$$$ time for each odd stick.

Case 3: The line of symmetry intersects exactly two sticks.

Let the longer of the two sticks that intersect the line of symmetry be the long odd stick, and the shorter be the short odd stick. As long as the difference in the length of the long odd stick and even odd stick is less than the total length of the pairs of sticks with identical length, we can use the long odd stick and short odd stick.

Let's say the remaining sticks in ascending order are $$$v_1,v_2,\ldots,v_k\ (v_1\lt v_2\lt\ldots\lt v_k)$$$. If the longer stick we choose is $$$v_i\ (i\gt 1)$$$, then the shorter one we choose should always be $$$v_{i-1}$$$, because it is the longest one we can choose and the difference of the two sticks chosen is minimized.

So you just need to check these pairs: $$$(v_1,v_2),(v_2,v_3),\ldots,(v_{k-1},v_k)$$$.

The time complexity is $$$\mathcal{O}(n\log n)$$$.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int MAXN = 200'005;
 
int t;
int n;
int a[MAXN];
map<int, int> cnt;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while (t--) {
        cnt.clear();
 
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n; i++) {
            cnt[a[i]]++;
        }
 
        ll base = 0;
        vector<int> odd, even;
        for (auto [x, c] : cnt) {
            base += (ll)x * (c / 2);
            if (c % 2 == 1) {
                odd.push_back(x);
            } else if (c >= 2) {
                even.push_back(x);
            }
        }
 
        if (base == 0) {
            cout << 0 << '\n';
            continue;
        }
 
        ll ans = 0;
        for (int x : odd) {
            if (2 * base > x) {
                ans = max(ans, 2 * base + x);
            }
        }
 
        assert(is_sorted(odd.begin(), odd.end()));
        for (int i = 1; i < (int)odd.size(); i++) {
            if (odd[i - 1] + 2 * base > odd[i]) {
                ans = max(ans, odd[i - 1] + 2 * base + odd[i]);
            }
        }
 
        for (int x : even) {
            if (base - x > 0) {
                ans = max(ans, 2 * base);
            }
        }
 
        cout << ans << '\n';
    }
    return 0;
}

import sys
input = lambda: sys.stdin.readline().strip()

t = int(input())
outs = []
 
# avoiding hash collisions, which we don't have tests in the pretests
rnd = random.getrandbits(30)
fmax = lambda x, y: x if x > y else y
 
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    
    cnt = Counter(x ^ rnd for x in nums)
    
    c = 0
    half = 0
    tmp = []
    
    for x in cnt:
        if cnt[x] > 1:
            c += cnt[x] // 2
            half += cnt[x] // 2 * (x ^ rnd)
        if cnt[x] % 2:
            tmp.append(x ^ rnd)
    
    tmp.sort()
    
    ans = 0 if c <= 1 else half * 2
    
    for x in tmp:
        if half * 2 > x:
            ans = fmax(ans, half * 2 + x)
    
    for i in range(1, len(tmp)):
        if half * 2 > tmp[i] - tmp[i - 1]:
            ans = fmax(ans, half * 2 + tmp[i - 1] + tmp[i])
    
    outs.append(ans)
 
print('\n'.join(map(str, outs)))

Break up a nice array into "blocks" of same values.

Each block can be considered as blocks of size $$$2$$$ and $$$3$$$ concatenating together.

We can divide the nice circular array in blocks, where each block consists of equal values.

The final circular array can be divided into blocks with size of at least $$$2$$$.

And, since $$$2=2,3=3,4=2+2$$$, each block can be divided into sub-blocks of size $$$2$$$ and $$$3$$$:

• If the block is of size $$$3k-1\ (k\gt 0)$$$, then $$$3k-1=1\cdot 2+(k-1)\cdot 3$$$.
• If the block is of size $$$3k\ (k\gt 0)$$$, then $$$3k=0\cdot 2+k\cdot 3$$$.
• If the block is of size $$$3k+1\ (k\gt 0)$$$, then $$$3k+1=2\cdot 2+(k-1)\cdot 3$$$.

With this observation, we can modify the condition of a nice circular array as follows:

A circular array is nice if we can split it into contiguous blocks of length 2 or length 3, such that each block has equal value, and each element belongs to exactly one block.

Let us first try to solve the easier problem where the array is not circular. Let $$$\text{dp}[i]$$$ be the minimum number of operations to make $$$[a_1,a_2,\ldots,a_i]$$$ nice. Then, by considering whether the last block containing $$$a_i$$$ is of length $$$2$$$ or length $$$3$$$, we can come up with the transition:

where $$$\text{cost}$$$ denotes the minimum number of operations to make the elements equal.

To solve the original problem where the array is circular, we can use the standard technique of splitting the circular array by cutting the circle between $$$(i, i + 1)$$$ for each $$$1\le i\le n$$$. This will take $$$\mathcal{O}(n^2)$$$ time. However, since the length of the blocks do not exceed $$$3$$$, we only need to try three splitting points $$$(1, 2)$$$, $$$(2, 3)$$$, and $$$(3, 4)$$$.

The time complexity is $$$\mathcal{O}(n)$$$.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const ll LINF = 1000000000000000005;
const int MAXN = 500005;
 
int t;
int n;
int a[MAXN];
ll dp[MAXN];
 
ll cost(int x, int y) { return abs(x - y); }
 
ll cost(int x, int y, int z) {
    if (x > y) {
        swap(x, y);
    }
    if (y > z) {
        swap(y, z);
    }
    if (x > y) {
        swap(x, y);
    }
    return z - x;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
 
        ll ans = LINF;
        for (int cyc = 0; cyc < 4; cyc++) {
            dp[0] = 0;
            dp[1] = LINF;
            for (int i = 2; i <= n; i++) {
                dp[i] = dp[i - 2] + cost(a[i - 1], a[i]);
                if (i >= 3) {
                    dp[i] =
                        min(dp[i], dp[i - 3] + cost(a[i - 2], a[i - 1], a[i]));
                }
            }
            ans = min(ans, dp[n]);
 
            // cyclic shift anti-clockwise
            for (int i = 2; i <= n; i++) {
                swap(a[i], a[i - 1]);
            }
        }
 
        cout << ans << '\n';
    }
    return 0;
}

import sys
input = lambda: sys.stdin.readline().strip()

t = int(input())
outs = []
fmin = lambda x, y: x if x < y else y
 
inf = 10 ** 15
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    
    ans = inf
    
    for _ in range(3):
        nums = nums[-1:] + nums[:-1]
        dp = [inf] * (n + 1)
        dp[0] = 0
        
        for i in range(2, n + 1):
            dp[i] = fmin(dp[i - 2] + max(nums[i-2:i]) - min(nums[i-2:i]),
                         dp[i - 3] + max(nums[i-3:i]) - min(nums[i-3:i]) if i >= 3 else inf)
        
        ans = fmin(ans, dp[n])
    
    outs.append(ans)
 
print('\n'.join(map(str, outs)))

Why is the answer always smaller than $$$10^{100}$$$ ?

There are only a few $$$k$$$-s that are worth choosing.

$$$f_m(x, n)$$$ is equal to $$$0$$$ for a lot of the $$$x$$$.

Let $$$p_0$$$ be the largest prime that is not greater than $$$n$$$. Then, $$$f_m(x, n) = 0$$$ for all $$$x \lt p_0$$$.

Let $$$\mathrm{PrimeGap}(M)$$$ be the maximum difference between a number $$$x\ (2\leq x\leq M)$$$ and the largest prime number no larger than it. We only need to compute $$$\mathrm{PrimeGap}(n) \le \mathrm{PrimeGap}(10^7) = 152$$$ values of $$$f_m(x, n)$$$. As this is reasonably small, we will now try to calculate the value of each $$$f_m(x, n)$$$ for all possible $$$x \ge p_0$$$.

First, we state a simple but useful lemma: for all $$$k\ge 2$$$, $$$v_k(a!) \le v_k(b!)$$$ if $$$a\le b$$$.

To find out some more about $$$w_k(a,b)$$$, let's factor $$$k$$$ as $$$k=p_1^{v_1}p_2^{v_2}\ldots p_t^{v_t}$$$ where $$$p_1,p_2,\ldots,p_t$$$ are disctinct primes and $$$v_1,v_2,\ldots,v_t$$$ are positive integers.

Then, $$$w_k(a,b)\geq\min\limits_i w_{p_i^{v_i}}(a,b)$$$.

Since $$$f_m(a, b)$$$ considers the minimum of $$$w_k(a, b)$$$ over all $$$2\le k\le m$$$, we only need to consider $$$k$$$ that are primes, or powers of primes. Formally, we only need to consider integers of the form $$$p^v$$$ where $$$p$$$ is a prime number and $$$v$$$ is a positive integer.

Furthermore, we only need to consider numbers of the form $$$p^v$$$ where $$$p$$$ is a prime number and $$$p$$$ divides at least one of the numbers in $$$[p_0, n]$$$.

There are $$$\mathcal{O}(\mathrm{PrimeGap}(n)\log_2 n)$$$ primes $$$p$$$ that divide at least one of the numbers in $$$[p_0, n]$$$. We can calculate the value of $$$v_p(x!)$$$ and $$$v_p(n!)$$$ in $$$\mathcal{O}(\log_2 n)$$$ using the given formula. For each prime $$$p$$$, there are at most $$$\mathcal{O}(\log_2 m)$$$ prime powers $$$p^v \le m$$$, and $$$v_{p^k}(x!)$$$ and $$$v_{p^k}(n!)$$$ can both be calculated in $$$\mathcal{O}(1)$$$ time after computing $$$v_p(x!)$$$ and $$$v_p(n!)$$$ in the previous step. Hence, a single $$$f_m(x, n)$$$ can be computed in $$$\mathcal{O}(\mathrm{PrimeGap}(n)\log_2 n(\log_2 n + \log_2 m))$$$ time.

The total time complexity if $$$\mathcal{O}(t\cdot \mathrm{PrimeGap}(n)^2\log_2 n(\log_2 n + \log_2 m))$$$. Even though this seems very big, the constant is very small, so it passess comfortably.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int MAXN = 10000005;
const int INF = 1000000005;
 
bool is_prime[MAXN];
 
inline int calc_v(int p, int x) {
    int res = 0;
    ll pw_p = p;
    while (pw_p <= x) {
        res += x / pw_p;
        pw_p *= p;
    }
    return res;
}
 
int t;
int n, m;
vector<int> small_primes;
 
int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    for (int i = 2; i < MAXN; i++) {
        is_prime[i] = true;
    }
    for (int p = 2; (ll)p * p < MAXN; p++) {
        if (!is_prime[p]) {
            continue;
        }
        small_primes.push_back(p);
        for (int i = p * p; i < MAXN; i += p) {
            is_prime[i] = false;
        }
    }
 
    cin >> t;
    while (t--) {
        cin >> n >> m;
 
        // find largest prime q <= n. Requires at most 142 iterations (due to
        // prime gap)
        int q = n;
        while (!is_prime[q]) {
            q--;
        }
 
        // precompute the useful big primes
        vector<int> useful_p;
        for (int f = 1; (ll)f * f <= n; f++) {
            // p_bnd is the largest possible value such that floor(n / p_bnd) =
            // f n / p_bnd >= f p_bnd <= n / f
            int p_bnd = n / f;
            int p = p_bnd;
            while (!is_prime[p]) {
                p--;
            }
            useful_p.push_back(p);
        }
 
        ll ans = 0;
        // for all x < q, f_m(x, n) = 0. try all x >= q
        for (int x = q; x < n; x++) {
            int res = INF;
 
            for (int p : useful_p) {
                int vx = calc_v(p, x), vn = calc_v(p, n);
                if (vx != vn) {
                    res = min(res, vx);
                }
            }
 
            for (int p : small_primes) {
                if ((ll)p * p > m) {
                    break;
                }
 
                int base_vx = calc_v(p, x), base_vn = calc_v(p, n);
                for (ll exp = 1, pw_p = p; pw_p <= m; exp++, pw_p *= p) {
                    int vx = base_vx / exp, vn = base_vn / exp;
                    if (vx != vn) {
                        res = min(res, vx);
                    }
                }
            }
 
            ans += res;
        }
 
        cout << ans << '\n';
    }
    return 0;
}

import sys
input = lambda: sys.stdin.readline().strip()

M = 10 ** 7
pr = [1] * (M + 1)
 
for i in range(2, M + 1):
    if pr[i] == 1:
        for j in range(i, M + 1, i):
            pr[j] = i

t = int(input())
outs = []

fmin = lambda x, y: x if x < y else y
 
inf = 10 ** 9
 
for _ in range(t):
    n, m = map(int(input().split()))
    
    vis = set()
    
    for i in range(n, 0, -1):
        x = i
        while x > 1:
            vis.add(pr[x])
            x //= pr[x]
        
        if pr[i] == i: break
    
    ans = 0
    
    def f(val, p):
        c = 0
        while val:
            val //= p
            c += val
        return c
    
    for i in range(n - 1, 0, -1):
        res = inf
        
        for v in vis:
            cur = v
            c = 1
            
            v1 = f(i, v)
            v2 = f(n, v)
            
            while cur <= m:
                
                if v1 // c != v2 // c:
                    res = fmin(res, v1 // c)
                
                cur *= v
                c += 1
        
        ans += res
        
        if pr[i] == i: break
    
    outs.append(ans)
 
print('\n'.join(map(str, outs)))

What does the condition "there do not exist four indices $$$1\leq i\lt j\lt k\lt l\leq m$$$ such that $$$b_i\neq b_j$$$, $$$b_i=b_k$$$ and $$$b_j=b_l$$$." reminds you of?

You can construct a tree based on the array. How can you do so?

The strange condition given by the problem is that there are no subsequences in the form of $$$[x,y,x,y]\ (x\neq y)$$$.

Let us construct a tree such that its DFS order $$$^\dagger$$$ is equal to $$$a$$$. We can build the tree as follows:

• Initialize a stack containing a vertex $$$0$$$.
• Iterate over the array $$$a$$$ from index $$$i = 1$$$ to $$$i = n$$$.
• For each element $$$a[i]$$$:
  • Add an edge between the vertex on top of the stack and vertex $$$i$$$. Assign vertex $$$i$$$ the value $$$a[i]$$$.
  • If this is the first occurrence of $$$a[i]$$$, push $$$i$$$ onto the stack.
  • If this is the last occurrence of $$$a[i]$$$, pop the top element from the stack (even if you have just pushed it).

Only the first and last occurrence of each value affects the stack. It can be proven that at the last occurence of each value, the vertex being popped from the stack will have the same value as the value of the processed vertex. This is because all elements in between the first and last occurrence of a value $$$x$$$ must be strictly contained in the range (due to the property of a cute array). Hence, all vertices that are pushed into the stack after the first occurrence of $$$x$$$ will be popped out before the last occurrence of $$$x$$$.

Due to the property of a cute array, the set of vertices with equal values forms a single connected component in the tre

Since there can only be one vertex in the stack for each value, all vertices of the same value have the same parent.

To answer the queries, we decompose the range $$$l$$$ to $$$r$$$ into three parts by considering the lowest common ancestor (LCA) of vertex $$$l$$$ and vertex $$$r$$$:

• From $$$l$$$ to LCA:
  • If $$$l$$$ has the same value as LCA, you can leave it to the second part.
  • Otherwise, let $$$l'$$$ be the child vertex of LCA which is an ancestor of $$$l$$$, and $$$\text{last}_{l'}$$$ be the vertex with the largest index in the subtree of $$$l'$$$. The values that appear in the subtree of $$$l'$$$ never occur in other parts of the tree. Hence, the answer for the subarray $$$a_{l\ldots \text{last}_{l'}}$$$ is equals to the answer for the suffix $$$a_{l\ldots n}$$$ minus the answer for the suffix $$$a_{\text{last}_{l'} + 1\ldots n}$$$. By precomputing the answer for each suffix of the entire array $$$a$$$, we can find the answer for subarray $$$a_{l\ldots \text{last}_{l'}}$$$ in $$$\mathcal{O}(1)$$$ time.
• At LCA:
  • Let $$$r'$$$ be the child vertex of the LCA which is an ancestor of $$$r$$$. We want to compute the answer for the subarray $$$a_{\text{last}_{l'} + 1\ldots r'-1}$$$.
  • This can be done by considering the children of the LCA between $$$l'$$$ and $$$r'$$$, then summing up the answer for the subtrees of those children.
    • For subtrees that are a single vertex, they have the same value as the LCA. We can count the occurrence of the value between vertex $$$l'$$$ and $$$r'$$$ in $$$\mathcal{O}(1)$$$ time after precomputing prefix sums.
    • For other subtrees, the answer for their corresponding subarray is independent of the rest of the array. Hence, we can precompute the answer for the subtree of each vertex with a simple DFS. Then, we can sum up the answer for the subtrees of all children between $$$l'$$$ and $$$r'$$$ using perfix sums.
• From LCA to $$$r$$$:
  • This is handled in the same way as the first part, except that we need to precompute the answer for each prefix of the entire array instead of the suffix.

The time complexity is $$$\mathcal{O}(n+q\log n)$$$.

$$$^\dagger$$$ The DFS order of a tree is found by calling the following dfs function on the tree.

dfs_order = []

def dfs(v):
	dfs_order.append(v)
	# children[v] is the set of children of vertex v
	for child in children[v]:
		dfs(child)

dfs(0)

import sys
import bisect
input = lambda: sys.stdin.readline().strip()

t = int(input())
outs = []

fmax = lambda x, y: x if x > y else y
 
for _ in range(t):
    n, q = map(int, input().split())
    nums = [0] + list(map(int, input().split()))
    
    first_pos = [0] * (n + 1)
    last_pos = [0] * (n + 1)
    
    for i in range(n + 1):
        last_pos[nums[i]] = i
    
    for i in range(n, -1, -1):
        first_pos[nums[i]] = i
    
    path = [[] for _ in range(n + 1)]
    nth_parent = [[-1] * (n + 1) for _ in range(20)]
    depth = [0] * (n + 1)
    
    stk = [0]
    
    for i in range(1, n + 1):
        path[stk[-1]].append(i)
        nth_parent[0][i] = stk[-1]
        depth[i] = depth[stk[-1]] + 1
        
        if first_pos[nums[i]] == i:
            stk.append(i)
        if last_pos[nums[i]] == i:
            stk.pop()
    
    depth.append(-1)
    
    for i in range(19):
        for j in range(n + 1):
            if nth_parent[i][j] != -1:
                nth_parent[i + 1][j] = nth_parent[i][nth_parent[i][j]]
    
    cnt = [0] * (n + 1)
    cur = 0
    
    pref_val = [0] * (n + 1)
    
    for i in range(1, n + 1):
        cur += -nums[i] if cnt[nums[i]] else nums[i]
        cnt[nums[i]] ^= 1
        pref_val[i] = cur
    
    cnt = [0] * (n + 1)
    cur = 0
 
    suff_val = [0] * (n + 1)
    
    for i in range(n, 0, -1):
        cur += -nums[i] if cnt[nums[i]] else nums[i]
        cnt[nums[i]] ^= 1
        suff_val[i - 1] = cur
 
    subtree_val = [0] * (n + 1)
    subtree_max_idx = list(range(n + 1))
    
    for i in range(n, -1, -1):
        if first_pos[nums[i]] == i:
            c = 1
            total = 0
            
            for j in path[i]:
                total += subtree_val[j]
                if nums[j] == nums[i]:
                    c ^= 1
                subtree_max_idx[i] = fmax(subtree_max_idx[i], subtree_max_idx[j])
            
            subtree_val[i] = total + c * nums[i]
    
    accs = [[0] * (len(path[i]) + 2) if first_pos[nums[i]] == i else [] for i in range(n + 1)]
    
    for i in range(n + 1):
        if first_pos[nums[i]] == i:
            total = 0
            c = 1
            accs[i][1] = total * 2 + c
            
            for j in range(len(path[i])):
                total += subtree_val[path[i][j]]
                if nums[path[i][j]] == nums[i]:
                    c ^= 1
                accs[i][j + 2] = total * 2 + c
    
    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        d = depth[u] - depth[v]
        
        while d:
            x = d & -d
            bit = x.bit_length() - 1
            u = nth_parent[bit][u]
            d -= x
        
        if u == v: return u
        
        for i in range(19, -1, -1):
            if nth_parent[i][u] != nth_parent[i][v]:
                u = nth_parent[i][u]
                v = nth_parent[i][v]
 
        return nth_parent[0][u]
    
    last = 0
    ans = [0] * q
    
    for idx in range(q):
        l, r = map(int, input().split())
        l = (l + last - 1) % n + 1
        r = (r + last - 1) % n + 1
        
        if l > r: l, r = r, l
        ancestor = lca(l, r)
 
        if l == r:
            last = nums[l]
        else:
            last = 0
            
            if l == ancestor and first_pos[nums[l]] == l:
                pl = 0
            elif nth_parent[0][l] == ancestor and first_pos[nums[ancestor]] == ancestor and first_pos[nums[l]] != l:
                pl = bisect.bisect_left(path[ancestor], l) + 1
            else:
                cl = l
                for i in range(19, -1, -1):
                    if depth[nth_parent[i][cl]] > depth[ancestor]:
                        cl = nth_parent[i][cl]
                last += suff_val[l - 1] - suff_val[subtree_max_idx[cl]]
                pl = bisect.bisect_left(path[ancestor], cl) + 2
            
            if r == ancestor and first_pos[nums[r]] == r:
                pr = 0
            elif nth_parent[0][r] == ancestor and first_pos[nums[ancestor]] == ancestor and first_pos[nums[r]] != r:
                pr = bisect.bisect_left(path[ancestor], r) + 1
            else:
                cr = r
                for i in range(19, -1, -1):
                    if depth[nth_parent[i][cr]] > depth[ancestor]:
                        cr = nth_parent[i][cr]
                last += pref_val[r] - pref_val[cr - 1]
                pr = bisect.bisect_left(path[ancestor], cr)
 
            xl = accs[ancestor][pl]
            xr = accs[ancestor][pr + 1]
            
            vl, cl = divmod(xl, 2)
            vr, cr = divmod(xr, 2)
            
            last += vr - vl + (cl ^ cr) * nums[ancestor]
 
        ans[idx] = last
    
    outs.append(' '.join(map(str, ans)))
 
print('\n'.join(outs))

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
namespace solution {
 
const int MAXL = 21;
const int MAXN = 1000005;
 
int n, q;
int a[MAXN];
vector<int> occ[MAXN];
ll pfx[MAXN], sfx[MAXN];
ll sm_pfx[MAXN], sm_sfx[MAXN];
 
inline bool is_first_occ(int i) { return occ[a[i]][0] == i; }
inline bool is_last_occ(int i) { return occ[a[i]].back() == i; }
// returns minimum j >= p such that a[j] == x, or n + 1 if does not exist
inline auto nxt_occ(int p, int x) {
    return lower_bound(occ[x].begin(), occ[x].end(), p);
}
 
int p[MAXL][MAXN];
vector<int> adj[MAXN];
inline void add_edge(int u, int v) {
    p[0][v] = u;
    adj[u].push_back(v);
}
 
int lvl[MAXN];
void dfs(int u) {
    for (int l = 1; l < MAXL; l++) {
        p[l][u] = p[l - 1][p[l - 1][u]];
    }
    if (u) {
        sm_pfx[u] += pfx[u];
        auto ptr = nxt_occ(u + 1, a[u]);
        sm_sfx[u] += ptr == occ[a[u]].end() ? 0 : sfx[*ptr];
    }
    for (int v : adj[u]) {
        lvl[v] = lvl[u] + 1;
        sm_pfx[v] = sm_pfx[u];
        sm_sfx[v] = sm_sfx[u];
        dfs(v);
    }
}
 
tuple<int, int, int> get_lca(int a, int b) {
    bool swp = false;
    if (lvl[a] < lvl[b]) {
        swap(a, b);
        swp = true;
    }
    for (int l = MAXL - 1; l >= 0; l--) {
        if (lvl[p[l][a]] >= lvl[b]) {
            a = p[l][a];
        }
    }
    if (a == b) {
        return {a, -1, -1};
    }
    if (swp) {
        swap(a, b);
    }
    for (int l = MAXL - 1; l >= 0; l--) {
        if (p[l][a] != p[l][b]) {
            a = p[l][a];
            b = p[l][b];
        }
    }
    return {p[0][a], a, b};
}
 
ll solve_same_layer(int l, int r) {
    assert(p[0][l] == p[0][r]);
    ll res =
        (pfx[r] -
         ((nxt_occ(r + 1, a[l]) - occ[a[l]].begin()) % 2 == 1 ? a[l] : 0)) -
        (pfx[l] -
         ((nxt_occ(l, a[l]) - occ[a[l]].begin() + 1) % 2 == 1 ? a[l] : 0));
    if ((nxt_occ(r + 1, a[l]) - nxt_occ(l, a[l])) % 2 == 1) {
        res += a[l];
    }
    return res;
}
 
void precompute() {
    for (int i = 0; i <= n; i++) {
        occ[i].clear();
        adj[i].clear();
        pfx[i] = sfx[i] = sm_pfx[i] = sm_sfx[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        occ[a[i]].push_back(i);
    }
    vector<int> stk;
    stk.push_back(0);
    for (int i = 1; i <= n; i++) {
        if (!is_first_occ(i)) {
            assert(!stk.empty() && a[stk.back()] == a[i]);
            stk.pop_back();
        }
        assert(!stk.empty());
        add_edge(stk.back(), i);
        if (!is_last_occ(i)) {
            stk.push_back(i);
        }
    }
 
    for (int u = n; u >= 0; u--) {
        {
            ll prv = 0;
            for (int i = 0; i < (int)adj[u].size(); i++) {
                int v = adj[u][i];
                auto ptr = nxt_occ(v, a[v]);
                pfx[v] =
                    prv + ((ptr - occ[a[v]].begin() + 1) % 2 == 1 ? a[v] : 0);
                if (!adj[v].empty()) {
                    prv += pfx[adj[v].back()];
                }
                if (is_last_occ(v)) {
                    prv += occ[a[v]].size() % 2 == 1 ? a[v] : 0;
                }
            }
        }
        {
            ll prv = 0;
            for (int i = (int)adj[u].size() - 1; i >= 0; i--) {
                int v = adj[u][i];
                auto ptr = nxt_occ(v, a[v]);
                if (!adj[v].empty()) {
                    prv += sfx[adj[v][0]];
                }
                sfx[v] = prv + ((occ[a[v]].end() - ptr) % 2 == 1 ? a[v] : 0);
                if (is_first_occ(v)) {
                    prv += occ[a[v]].size() % 2 == 1 ? a[v] : 0;
                }
            }
        }
    }
 
    dfs(0);
}
 
void init(int _n, int _q, vector<int> _a) {
    n = _n;
    q = _q;
    for (int i = 1; i <= n; i++) {
        a[i] = _a[i - 1];
    }
    precompute();
}
 
ll query(int l, int r) {
    if (l == r) {
        return a[l];
    }
    auto [lca, lc, rc] = get_lca(l, r);
    assert(lca != r);
    if (lca == l) {
        ll ans = sm_pfx[r] - sm_pfx[l] + a[l];
        return ans;
    } else if (lc == l) {
        ll ans = sm_pfx[r] - sm_pfx[rc];
        ans += solve_same_layer(l, rc);
        return ans;
    } else {
        ll ans = sfx[l] + sm_sfx[p[0][l]] - sm_sfx[lc] + sm_pfx[r] - sm_pfx[rc];
        ans += solve_same_layer(*nxt_occ(lc + 1, a[lc]), rc);
        return ans;
    }
}
 
} // namespace solution
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
 
        solution::init(n, q, a);
        ll prv_ans = 0;
        while (q--) {
            int l, r;
            cin >> l >> r;
            auto decode = [&](int x) { return (x - 1 + prv_ans) % n + 1; };
            l = decode(l);
            r = decode(r);
            if (l > r) {
                swap(l, r);
            }
            ll ans = solution::query(l, r);
            cout << ans << ' ';
            prv_ans = ans;
        }
        cout << '\n';
    }
    return 0;
}