/*
Time limit: 5000ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_N 131072
/**
* @brief Check if array a[l..r] is a magic array (any c)
* Use divide and conquer: recursively check both halves
* @param l left bound (0-indexed)
* @param r right bound (0-indexed)
* @return the value c if it's a c-magic array, or -1 if not magic
*/
int check_magic(int* a, int l, int r) {
// WRITE YOUR CODE HERE
}
/**
* @brief Solve the problem by checking if the array is a magic array
* @param a the array
* @param n the length of the array
* @return the value c if it's a c-magic array, or -1 if not magic
*/
int solve(int* a, int n) {
// WRITE YOUR CODE HERE
}
int main(void) {
int t;
scanf("%d", &t);
int* a;
a = (int*)malloc(MAX_N * sizeof(int));
while (t--) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
int result = solve(a, n);
printf("%d\n", result);
}
free(a);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Magic Array
You are given an array $a[0..n-1]$ of $n$ integers. It is guaranteed that $n = 2^k$ for some integer $k \geq 0$.
The array $a[0..n-1]$ is called a $c$-magic array if at least one of the following conditions is satisfied:
1. The length of the array is 1, and $a[0] = c$;
2. The length of the array is greater than 1, the first half of the array is a $c$-magic array, and the second half of the array is a $(c+1)$-magic array;
3. The length of the array is greater than 1, the second half of the array is a $c$-magic array, and the first half of the array is a $(c+1)$-magic array.
For example: $[2, 1, 3, 2]$ is a $1$-magic array.
Your task is to determine whether the given array is a $c$-magic array for some integer $c$. If yes, output the value $c$; otherwise, output $-1$.
**Hint**: Use a divide-and-conquer algorithm to solve this problem recursively.
### Input
- First line contains one integer $t$ ($1 \leq t \leq 1000$): the number of test cases
- For each test case:
- First line contains one integer $n$ ($1 \leq n \leq 131072$): the length of the array. It is guaranteed that $n = 2^k$ for some integer $k \geq 0$
- Second line contains $n$ integers $a_0, a_1, \ldots, a_{n-1}$ ($0 \leq a_i \leq 10^5$): the array elements
It is guaranteed that the sum of $n$ over all test cases does not exceed $5\times 10^6$.
### Output
For each test case, output one integer:
- If the array is a $c$-magic array for some integer $c$, output $c$
- Otherwise, output $-1$
### Example
**Input**
```
2
4
2 1 3 2
4
1 2 3 4
```
**Output**
```
1
-1
```
**Explanation**
For the first test case, array $[2, 1, 3, 2]$:
- The first half $[2, 1]$ is a $1$-magic array:
- The first half $[2]$ is a $2$-magic array (single element equals 2)
- The second half $[1]$ is a $1$-magic array (single element equals 1)
- Since first half is $2$-magic and second half is $1$-magic, $[2, 1]$ is $1$-magic
- The second half $[3, 2]$ is a $2$-magic array:
- The first half $[3]$ is a $3$-magic array (single element equals 3)
- The second half $[2]$ is a $2$-magic array (single element equals 2)
- Since first half is $3$-magic and second half is $2$-magic, $[3, 2]$ is $2$-magic
- Since first half is $1$-magic and second half is $2$-magic, $[2, 1, 3, 2]$ is $1$-magic, so output $1$
For the second test case, array $[1, 2, 3, 4]$:
- The first half $[1, 2]$ is a $1$-magic array (first half $[1]$ is $1$-magic, second half $[2]$ is $2$-magic)
- The second half $[3, 4]$ is a $3$-magic array (first half $[3]$ is $3$-magic, second half $[4]$ is $4$-magic)
- For the whole array to be magic, we need either:
- First half to be $c$-magic and second half to be $(c+1)$-magic, or
- First half to be $(c+1)$-magic and second half to be $c$-magic
- Since first half is $1$-magic and second half is $3$-magic, and $1+1 \neq 3$ and $3+1 \neq 1$, neither condition is satisfied
- Therefore, output $-1$