hackercupai/hackercup huggingface dataset:
**Note: This is the harder version of [Chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-2/problems/A1). This version involves an array of integers instead of a string, and the array may change with updates.**

An array is *perfectly balanced* if its length is even, and the first half of the array can be shuffled to make the array a palindrome. For example, \([15,2,15,2]\) and \([7,5,5,7]\) are perfectly balanced, but \([7,5,3,1,3,5,7]\) and \([3,1,1,3,2,3]\) are not.

An array is *almost perfectly balanced* if you can delete exactly one element from it to make it perfectly balanced. Some examples are \([1, 2, 3, 4, 4, 5, 1, 3, 2]\), \([1]\), and \([2, 2, 2, 3, 2]\).

{{PHOTO_ID:532712048616543|WIDTH:700}}

You are given a larger template array \(A_1 ... A_N\) of length \(N\), along with \(Q\) events, the \(i\)th of which is one of the following two formats:

- \(1\) \(X_i\) \(Y_i\): set \(A_{X_i}\) to \(Y_i\).
- \(2\) \(L_i\) \(R_i\): check whether the subarray \(A_{L_i..R_i}\) is almost perfectly balanced.

For how many type-2 queries is the subarray almost perfectly balanced?

# Constraints

\(1 \le T \le 85\)
\(1 \le N \le 10^6\)
\(1 \le A_i \le 10^6\)
\(1 \le Q \le 10^6\)
\(1 \le X_i \le N\)
\(1 \le Y_i \le 10^6\)
\(1 \le L_i \le R_i \le N\)

The sum of \(N\) across all test cases is at most \(4{,}000{,}000\).
The sum of \(Q\) across all test cases is at most \(4{,}000{,}000\).

# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing a single integer \(N\). Then, there is a line containing \(N\) space-separated integers \(A_1, ..., A_N\). Then, there is a line containing a single integer \(Q\). Then, \(Q\) lines follow, the \(i\)th of which contains three space-separated integers, either "\(1\) \(X_i\) \(Y_i\)" or "\(2\) \(L_i\) \(R_i\)".

# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "`, followed by a single integer: the number of queries which are an almost perfectly balanced subarray.

# Sample Explanation

In the first case, the template array is \([2,1,5,1,5,1]\).

For the first query, the subarray is \([1,5,1,5,1]\). You can delete the second \(1\) to get \([1,5,5,1]\), which is a palindrome. Thus, \([1,5,1,5,1]\) is an almost perfectly balanced subarray.

For the second query, the subarray is \([2,1,5,1,5]\). You can delete the \(2\) to get \([1,5,1,5]\) then reorder the first half of the array to get \([5,1,1,5]\), which is a palindrome. Thus, \([2,1,5,1,5]\) is an almost perfectly balanced subarray.

For the third query, the subarray is \([2,1,5]\). You cannot delete any element to get an almost perfectly balanced subarray.

The next two events are updates, after which the template array is \([5, 5, 5, 1, 5, 1]\).

For the fourth query, the subarray is \([5,5,5]\). You can delete any element to get \([5,5]\), which is a palindrome. Thus, \([5,5,5]\) is an almost perfectly balanced subarray.

The fifth, sixth, eighth, and tenth queries are also almost perfectly balanced subarrays, so the final answer is \(7\).