To construct a Xorion with exactly $$$k$$$ peaks:

• Use the largest $$$k$$$ elements from $$$n$$$ down to $$$n-k+1$$$ to form the peaks.
• Place the smaller numbers between them to create valleys.

Peak Definition

An index $$$i$$$ is a peak if: - $$$a_i \gt a_{i-1} \quad \text{and} \quad a_i \gt a_{i+1}$$$

Construction Pattern

We can build the sequence as:

• $$$1, n, 2, n-1, 3, n-2, \dots, n-k+1, k+1, k+2, \dots, n-k$$$

  • $$$n, n-1, \dots, n-k+1$$$ → largest $$$k$$$ numbers → peaks
  • $$$1, 2, \dots, k$$$ → smaller numbers → valleys
  • Remaining numbers $$$(k+1, k+2, \dots, n-k)$$$ → fill the rest

Feasibility Condition

• For this construction to be valid:

  • $$$n - k + 1 \gt k + 1 \quad \implies \quad 2 \cdot k \lt n$$$

• If $$$2 \cdot k \ge n$$$, it is impossible to form exactly $$$k$$$ peaks → output -1.

Example

• Let $$$n = 7$$$, $$$k = 2$$$

  1. Largest 2 numbers for peaks: $$$7, 6$$$
  2. Smaller numbers for valleys: $$$1, 2$$$
  3. Remaining numbers: $$$3, 4, 5$$$

Construction:

• $$$1, 7, 2, 6, 3, 4, 5$$$

• Peaks at indices 2 and 4:

  • $$$a_2 = 7 \gt 1, 2$$$
  • $$$a_4 = 6 \gt 2, 3$$$

Summary

• Use largest numbers for peaks

• Interleave smaller numbers for valleys

• Check feasibility: $$$2 \cdot k \lt n$$$

• If not possible → output -1

test = int(input())
for _ in range(test):
    n, k = map(int, input().split())
    
    if 2 * k >= n:
        print(-1)
        continue
    
    ans = []
    left = 1          
    right = n         
    
    for i in range(k):
        ans.append(left)
        ans.append(right)
        left += 1
        right -= 1
    
    for num in range(left, right + 1):
        ans.append(num)
    
    print(*ans)

We are asked to find a number in an array $$$a = [a_1, a_2, \dots, a_n]$$$ such that all array elements are divisible by it. If no such number exists, print -1. If multiple exist, any is acceptable.

Approach 1: Using GCD

Idea

• A number that divides all elements is a common divisor of the array.
• The greatest common divisor (GCD) of the array is the largest number that divides all elements.
• Steps:

1. Compute $$$g = \text{GCD}(a_1, a_2, \dots, a_n)$$$

2. Check if $$$g$$$ exists in the array:

   • If yes, output $$$g$$$
   • If no, output -1

Approach 2: Using Minimum Value

Idea

• Observation: If $$$a_i$$$ divides $$$a_j$$$, then $$$a_i \le a_j$$$.
• Therefore, the number that divides all other elements must be the minimum element in the array.

• Steps:

1. Find the minimum element from the array

2. Check if every element in the array is divisible by min_val:

   • If yes, output min_val
   • If no, output -1

from math import gcd

n = int(input())
arr = list(map(int, input().split()))

# a_gcd --> GCD of the given array 'arr'
a_gcd = arr[0]

for curr_num in arr:
    a_gcd = gcd(a_gcd, curr_num)
    
# Check if the GCD Exists on the array
is_found = False
for curr_num in arr:
    if curr_num == a_gcd:
        is_found = True
        break


if  is_found :
    print(a_gcd)
else:
    print(-1)     
    
"""
Even though this code is a working solution, the time complexity is:
- For each element, we calculate the GCD iteratively.
- Time complexity of gcd(a, b) is O(log(min(a, b)))
- Overall time complexity: O(n log(max_value))
"""

n = int(input())
arr = list(map(int, input().split()))

# Find the minimum value in the array
min_value = float("inf")
for curr_num in arr:
    min_value = min(min_value, curr_num)
    
# Check if the minimum value divides all elements
is_valid = True
for curr_num in arr:
    if curr_num % min_value != 0:
        is_valid = False
        break

if is_valid:
    print(min_value)
else:
    print(-1)

"""
Time Complexity:
- Finding the minimum value: O(n)
- Checking divisibility for all elements: O(n)
- Overall: O(n) 
Space Complexity: O(1)


"""