There are n heaps of stone. The i-th heap has h_i stones. You want to change the number of stones in the heap by performing the following process once: 

  * You go through the heaps from the 3-rd heap to the n-th heap, in this order. 
  * Let i be the number of the current heap. 
  * You can choose a number d (0 ≤ 3 ⋅ d ≤ h_i), move d stones from the i-th heap to the (i - 1)-th heap, and 2 ⋅ d stones from the i-th heap to the (i - 2)-th heap. 
  * So after that h_i is decreased by 3 ⋅ d, h_{i - 1} is increased by d, and h_{i - 2} is increased by 2 ⋅ d. 
  * You can choose different or same d for different operations. Some heaps may become empty, but they still count as heaps. 



What is the maximum number of stones in the smallest heap after the process?

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 2⋅ 10^5). Description of the test cases follows.

The first line of each test case contains a single integer n (3 ≤ n ≤ 2 ⋅ 10^5).

The second lines of each test case contains n integers h_1, h_2, h_3, …, h_n (1 ≤ h_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, print the maximum number of stones that the smallest heap can contain.

Example

Input


4
4
1 2 10 100
4
100 100 100 1
5
5 1 1 1 8
6
1 2 3 4 5 6


Output


7
1
1
3

Note

In the first test case, the initial heap sizes are [1, 2, 10, 100]. We can move the stones as follows. 

  * move 3 stones and 6 from the 3-rd heap to the 2-nd and 1 heap respectively. The heap sizes will be [7, 5, 1, 100]; 
  * move 6 stones and 12 stones from the last heap to the 3-rd and 2-nd heap respectively. The heap sizes will be [7, 17, 7, 82]. 



In the second test case, the last heap is 1, and we can not increase its size.

In the third test case, it is better not to move any stones.

In the last test case, the final achievable configuration of the heaps can be [3, 5, 3, 4, 3, 3].

Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
from sys import setrecursionlimit
from bisect import bisect_left, bisect_right
from collections import deque
from functools import lru_cache, reduce
from heapq import heappush, heappop
from math import sqrt, ceil, floor, log2
T = int(input())

def rl(t=int):
	return list(map(t, input().split()))

def feasible(a, m):
	og = a[:]
	for i in range(len(a) - 1, 1, -1):
		if a[i] < m:
			return False
		d = floor((a[i] - m) // 3)
		if og[i] < 3 * d:
			d = og[i] // 3
		a[i - 1] += d
		a[i - 2] += 2 * d
		a[i] -= 3 * d
	return min(a[0], a[1]) >= m
for t in range(1, T + 1):
	n = int(input())
	a = rl()
	(i, j) = (min(a), max(a))
	while i < j - 1:
		m = (i + j) // 2
		if feasible(a[:], m):
			i = m
		else:
			j = m - 1
	print(j if feasible(a, j) else i)


import sys, os
import math
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
from io import BytesIO, IOBase
from heapq import *
from bisect import *
from collections import *

def factors(n):
	i = 1
	ans = []
	while i < int(n ** 0.5) + 1:
		if n % i == 0:
			ans.append(i)
			if n // i != i:
				ans.append(n // i)
		i += 1
	return ans

def check(arr, k):
	temp = [0, 0]
	for i in range(len(arr) - 1, -1, -1):
		if arr[i] + temp[0] + 2 * temp[1] < k:
			return False
		t = min(arr[i] + temp[0] + 2 * temp[1] - k, arr[i])
		temp[1] = temp[0]
		temp[0] = t // 3
		if i == 1:
			temp[0] = 0
	return True

def main():
	for _ in range(mi()):
		n = mi()
		a = list(MI())
		lo = 0
		hi = 10 ** 10
		while lo + 1 < hi:
			mid = (lo + hi) // 2
			if check(a, mid):
				lo = mid
			else:
				hi = mid
		print(lo)
BUFSIZE = 8192

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, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

def mi():
	return int(input())

def outP(var):
	sys.stdout.write(str(var) + '\n')
MOD = 10 ** 9 + 7
mod = 998244353
main()


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	n = I()
	a = L()
	l = 0
	r = max(a)
	ans = min(a)
	while l <= r:
		m = (l + r) // 2
		f = 1
		b = a[:]
		d = [0] * n
		for i in range(n - 1, 1, -1):
			t = min(b[i], max(0, b[i] + d[i] - m)) // 3
			b[i] -= 3 * t
			d[i - 1] += t
			d[i - 2] += 2 * t
		for i in range(n):
			if b[i] + d[i] < m:
				f = 0
				break
		if f == 1:
			ans = max(m, ans)
			l = m + 1
		else:
			r = m - 1
	print(ans)


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
	return int(input())

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

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
import itertools
from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def S():
	return list(map(str, input().strip()))

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop, heappush
import bisect
from math import factorial, inf
from itertools import groupby
from itertools import permutations as comb
mod = 1000000007
MOD = 998244353

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a, b, c):
	print(c, a, b, flush=True)
	n = I()
	return n

def linear_sieve(n):
	is_composite = [False] * n
	prime = []
	for i in range(2, n):
		if not is_composite[i]:
			prime.append(i)
		for j in prime:
			is_composite[i * j] = True
			if i % prime == 0:
				break
	return prime

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 2:
		l.append(n)
	return l

def binpow(a, b, c):
	res = 1
	a = a % c
	while b > 0:
		if b & 1:
			res = res * a % c
		b = b >> 1
		a = a * a % c
	return res
d = []
primes = []
prim = [0] * (10 ** 5 + 1)

def sieve(n):
	for i in range(n):
		d.append(i)
	for i in range(2, n):
		if d[i] == i:
			prim[i] = 1
			primes.append(i)
		j = 0
		while j < len(primes) and primes[j] <= d[i] and (primes[j] * i < n):
			d[i * primes[j]] = primes[j]
			j += 1

def primeFactors(n):
	factors = []
	while n != 1:
		factors.append(d[n])
		n //= d[n]
	return factors
t = 1
t = I()
for _ in range(t):
	n = I()
	s = lint()
	(l, r) = (0, max(s))
	ans = min(s)
	while l <= r:
		m = (l + r) // 2
		z = s.copy()
		for i in range(n - 1, -1, -1):
			tmp = max(0, (z[i] - m) // 3)
			tmp = min(tmp, s[i] // 3)
			if i >= 2:
				z[i - 2] += 2 * tmp
				z[i - 1] += tmp
				z[i] -= 3 * tmp
		if min(z) < m:
			r = m - 1
		else:
			l = m + 1
			ans = m
	print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
BUFSIZE = 8192

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, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=10 ** 18, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

class LazySegUpdate:

	def __init__(self, N):
		self.N = N
		n = 4 * N
		self.tree = [0] * n
		self.lazy = [0] * n

	def queryHelper(self, index, s, e, l, r):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return 0
		if s >= l and e <= r:
			return self.tree[index]
		mid = (s + e) // 2
		return max(self.queryHelper(2 * index, s, mid, l, r), self.queryHelper(2 * index + 1, mid + 1, e, l, r))

	def updateHelper(self, index, s, e, l, r, h):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return
		if s >= l and e <= r:
			self.tree[index] = max(self.tree[index], h)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], h)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], h)
			return
		mid = (s + e) // 2
		self.updateHelper(2 * index, s, mid, l, r, h)
		self.updateHelper(2 * index + 1, mid + 1, e, l, r, h)
		self.tree[index] = max(self.tree[2 * index], self.tree[2 * index + 1])

	def query(self, l, r):
		return self.queryHelper(1, 0, self.N - 1, l, r - 1)

	def update(self, l, r, h):
		self.updateHelper(1, 0, self.N - 1, l, r - 1, h)

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
tt = 1
tt = int(input())
for _ in range(tt):
	n = int(input())
	a = list(map(int, input().split()))
	(l, r) = (min(a), max(a))
	ans = l
	while l <= r:
		mid = (l + r) // 2
		b = a.copy()
		m = 1
		for i in range(n - 1, 1, -1):
			if b[i] < mid:
				m = 0
				break
			d = min((b[i] - mid) // 3, a[i] // 3)
			b[i - 1] += d
			b[i - 2] += 2 * d
		if m and b[0] >= mid and (b[1] >= mid):
			ans = mid
			l = mid + 1
		else:
			r = mid - 1
	print(ans)


from bisect import bisect_left
import math
import os
import sys
from io import BytesIO, IOBase
M = 1000000007
import random
import heapq
import threading
import bisect
import time
from functools import *
from collections import *
from itertools import *
BUFSIZE = 8192
import array

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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())

class SortedList:

	def __init__(self, iterable=None, _load=200):
		if iterable is None:
			iterable = []
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def mex(arr):
	len1 = len(arr)
	lo = 0
	hi = len1 - 1
	ans = -1
	while lo <= hi:
		mid = (lo + hi) // 2
		if arr[mid] == mid:
			ans = mid + 1
			lo = mid + 1
		else:
			ans = mid
			hi = mid - 1
	return ans

def pos(arr, mid, n):
	arr2 = arr.copy()
	for i in range(n - 1, 1, -1):
		if arr[i] < mid:
			return False
		p = min(arr2[i], arr[i] - mid)
		p -= p % 3
		d = p // 3
		arr[i] -= p
		arr[i - 1] += d
		arr[i - 2] += 2 * d
	if max(arr2[0], arr[0]) < mid or max(arr2[1], arr[1]) < mid:
		return False
	return True

def main():
	tt = 1
	tt = inpu()
	for _ in range(tt):
		n = inpu()
		arr = lis()
		lo = 0
		hi = 10 ** 9
		ans = -1
		p = arr[:]
		while lo <= hi:
			mid = (lo + hi) // 2
			arr = p[:]
			if pos(arr, mid, n):
				ans = mid
				lo = mid + 1
			else:
				hi = mid - 1
		print(ans)
main()


from sys import stdin
input = stdin.readline

def check(x):
	value = a[:]
	for i in range(n - 1, 1, -1):
		if value[i] < x:
			return False
		this = min(a[i] // 3, max(0, (value[i] - x) // 3))
		value[i - 1] += this
		value[i - 2] += 2 * this
		value[i] -= 3 * this
	if value[0] < x or value[1] < x:
		return False
	return True

def answer():
	(l, h) = (0, max(a))
	while l <= h:
		mid = (l + h) // 2
		if check(mid):
			ans = mid
			l = mid + 1
		else:
			h = mid - 1
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def judge(target, arr):
	n = len(arr)
	copyarr = arr[:]
	for i in range(n - 1, -1, -1):
		more = min(copyarr[i] - target, arr[i])
		if more < 0:
			return False
		if more < 3:
			continue
		if i < 2:
			continue
		copyarr[i - 1] += more // 3
		copyarr[i - 2] += more // 3 * 2
		copyarr[i] -= more // 3 * 3
	return True

def main(t):
	n = int(input())
	arr = list(map(int, input().split()))
	front = 0
	rear = max(arr) + 1
	while front < rear:
		mid = (front + rear) // 2
		flag = judge(mid, arr)
		if judge(mid, arr):
			front = mid + 1
		else:
			rear = mid
	ans = front - 1
	print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

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

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

def possible(k, a):
	b = a[:]
	n = len(a)
	extrasum = [0] * n
	for i in range(n - 1, 1, -1):
		get = min(b[i], b[i] + extrasum[i] - k)
		if get < 0:
			return 0
		qu = get // 3
		b[i] -= 3 * qu
		extrasum[i - 1] += qu
		extrasum[i - 2] += qu * 2
	for i in range(n):
		if extrasum[i] + b[i] < k:
			return 0
	return 1
t = inp()
while t:
	t -= 1
	n = inp()
	a = lis()
	l = 1
	r = a[-1]
	r += 2
	ans = 0
	while l <= r:
		mid = (l + r) // 2
		if possible(mid, a):
			l = mid + 1
			ans = max(ans, mid)
		else:
			r = mid - 1
	print(ans)


def main():

	def checkPossible(stones):
		a = h.copy()
		for i in range(n - 1, 1, -1):
			if a[i] < stones:
				return False
			d = min((a[i] - stones) // 3, h[i] // 3)
			a[i] -= 3 * d
			a[i - 1] += d
			a[i - 2] += 2 * d
		return a[0] >= stones and a[1] >= stones
	t = int(input())
	allans = []
	for _ in range(t):
		n = int(input())
		h = readIntArr()
		avg = (sum(h) + n - 1) // n
		twoPowers = []
		b = 1
		while b <= avg:
			twoPowers.append(b)
			b *= 2
		twoPowers.reverse()
		ans = 0
		for b in twoPowers:
			if ans + b <= avg and checkPossible(ans + b):
				ans += b
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
	print('? {} {} {}'.format(a, b, c))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ansArr):
	print('! {}'.format(' '.join([str(x) for x in ansArr])))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
	main()


import sys
import math
from itertools import accumulate

def read_string():
	return sys.stdin.readline().strip()

def read_int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def solve():
	n = int(input())
	H = read_int_arr()

	def possible(val):
		ar = list(H)
		for j in range(n - 1, 1, -1):
			if ar[j] < val:
				return False
			diff = min(ar[j] - val, H[j])
			diff -= diff % 3
			ar[j] -= diff
			ar[j - 1] += diff // 3
			ar[j - 2] += 2 * (diff // 3)
		if ar[0] < val or ar[1] < val:
			return False
		return True

	def get_mini(val):
		ar = list(H)
		for j in range(n - 1, 1, -1):
			diff = min(ar[j] - val, H[j])
			diff -= diff % 3
			ar[j] -= diff
			ar[j - 1] += diff // 3
			ar[j - 2] += 2 * (diff // 3)
		mini = ar[0]
		for a in ar:
			mini = min(a, mini)
		return mini
	l = 0
	r = int(1000000000.0)
	while l < r - 1:
		m = (l + r) // 2
		if possible(m):
			l = m
		else:
			r = m - 1
	if possible(r):
		print(get_mini(r))
	else:
		print(get_mini(l))
T = int(input())
for _ in range(T):
	solve()


I = input
for _ in [0] * int(I()):
	(n, h, s, b) = (int(I()), [*map(int, I().split())], 1, 1 << 30)
	while b - s > 1:
		(m, u, i) = ((b + s) // 2, h[:], n)
		while i:
			i -= 1
			if u[i] < m:
				b = m
				break
			x = [0, min(h[i], u[i] - m) // 3][i > 1]
			u[i - 1] += x
			u[i - 2] += 2 * x
		else:
			s = m
	print(s)


import sys
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	n = int(sys.stdin.readline().strip())
	h = list(map(int, sys.stdin.readline().strip().split()))
	m = min(h)
	M = max(h)
	while m < M:
		x = (m + M + 1) // 2
		h1 = h[:]
		for i in range(2, n):
			if h1[n + 1 - i] < x:
				break
			else:
				d = min(h1[n + 1 - i] - x, h[n + 1 - i]) // 3
				h1[n + 1 - i] = h1[n + 1 - i] - 3 * d
				h1[n - i] = h1[n - i] + d
				h1[n - 1 - i] = h1[n - 1 - i] + 2 * d
		if min(h1) < x:
			M = x - 1
		else:
			m = x
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	stones = list(map(int, input().split()))
	(l, r) = (0, 10 ** 9 + 1)
	while abs(r - l) > 1:
		tmp = [0] * n
		tmp[0] = stones[0]
		tmp[1] = stones[1]
		mid = (l + r) // 2
		for i in range(n - 1, 1, -1):
			tmp[i] += stones[i]
			d = max(0, min((tmp[i] - mid) // 3, stones[i] // 3))
			tmp[i - 1] += d
			tmp[i - 2] += 2 * d
			tmp[i] -= 3 * d
		if min(tmp) < mid:
			r = mid
		else:
			l = mid
	print(l)


import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
(t,) = I()
for _ in range(t):
	(n,) = I()
	h = I()
	sml = 1
	big = 10 ** 9 + 1
	while big - sml > 1:
		mid = (big + sml) // 2
		use = [0] * n
		for i in range(n - 1, -1, -1):
			curr = h[i]
			if i + 1 < n:
				curr += use[i + 1]
			if i + 2 < n:
				curr += 2 * use[i + 2]
			if curr < mid:
				big = mid
				break
			if i > 1:
				use[i] = min(h[i], curr - mid) // 3
		else:
			sml = mid
	print(sml)


sr = lambda : input()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
inf = 10 ** 18
mod = 998244353
test = ir()
for t in range(test):
	n = ir()
	h = lr()
	h.reverse()

	def judge(x):
		margin = [0 for _ in range(n)]
		for i in range(n - 2):
			now_h = h[i]
			m = margin[i]
			d = min((now_h + m - x) // 3, now_h // 3)
			if d < 0:
				return False
			margin[i + 1] += d
			margin[i + 2] += 2 * d
		if h[-2] + margin[-2] >= x and h[-1] + margin[-1] >= x:
			return True
		else:
			return False
	l = min(h)
	r = max(h) + 1
	while r - l > 1:
		mid = l + (r - l) // 2
		if judge(mid):
			l = mid
		else:
			r = mid
	print(l)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
sys.setrecursionlimit(3 * 10 ** 5)
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
x = 0
pref = []
lvl = []
gp = []
ans = []

def hnbhai(tc):
	n = sb()
	a = sd()
	low = 0
	high = 10 ** 9
	ans = 0
	b = a.copy()
	while low <= high:
		for i in range(n):
			b[i] = a[i]
		mid = (low + high) // 2
		diff = []
		for i in range(n):
			diff.append(a[i] - mid)
		last = diff[-1]
		carry1 = 0
		carry2 = 0
		carry3 = 0
		carry4 = 0
		for i in range(n - 1, 1, -1):
			x = min(carry1 + carry2 + a[i] - mid, a[i])
			if x < 0:
				continue
			b[i] = a[i] + carry1 + carry2 - x
			x //= 3
			carry1 = x
			carry2 = carry3
			carry3 = 2 * x
		b[0] += carry3
		b[1] += carry1 + carry2
		fl = 0
		for i in b:
			if i < mid:
				fl = 1
				break
		if fl == 0:
			ans = mid
			low = mid + 1
		else:
			high = mid - 1
	print(ans)
	return
for _ in range(sb()):
	hnbhai(_ + 1)


def valid(heap, val):
	new_heap = [i for i in heap]
	for i in reversed(range(2, len(heap))):
		thing = max(min(heap[i] // 3, (new_heap[i] - val) // 3), 0)
		new_heap[i] -= 3 * thing
		new_heap[i - 1] += thing
		new_heap[i - 2] += 2 * thing
	for i in new_heap:
		if i < val:
			return False
	return True
for _ in range(int(input())):
	input()
	heap = list(map(int, input().split()))
	(start, end) = (0, max(heap) + 1)
	while start < end:
		mid = (start + end) // 2
		if mid == start or mid == end:
			break
		if valid(heap, mid):
			start = mid
		else:
			end = mid
	print(start)


from __future__ import print_function
from math import *
from collections import deque
import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

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, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	l = inlt()
	s = sum(l)
	a = s // n
	ans = min(l)
	l1 = l[:]
	low = 0
	high = 10 ** 9 + 7
	while low <= high:
		temp = [0] * n
		l = l1[:]
		a = (high + low) // 2
		for i in range(n - 1, 1, -1):
			if temp[i] + l[i] >= a:
				allo = min(l[i], temp[i] + l[i] - a)
				d = allo // 3
				temp[i - 1] += d
				temp[i - 2] += 2 * d
				l[i] -= 3 * d
		for i in range(n):
			l[i] = l[i] + temp[i]
		m = min(l)
		ans = max(ans, m)
		if m >= a:
			low = a + 1
		else:
			high = a - 1
	for i in range(n):
		l[i] = l[i] + temp[i]
	print(ans)


def verify(H, n, target):
	(d2, d1) = (0, 0)
	for i in range(2, n)[::-1]:
		(d2, d1, v) = (0, d2, H[i] + d1)
		if v < target:
			return False
		d = min((v - target) // 3, H[i] // 3)
		d2 += 2 * d
		d1 += d
	return H[0] + d2 >= target and H[1] + d1 >= target
for t in range(int(input())):
	n = int(input())
	H = tuple((int(v) for v in input().split()))
	lowerbound = min(H)
	upperbound = min(sum(H) // n, H[-1])
	for i in range(n - 2):
		upperbound = min(upperbound, H[i] + H[i + 1] // 3 + H[i + 2] // 3 * 2)
	upperbound = min(upperbound, H[-2] + H[-1] // 3)
	upperbound += 1
	while upperbound - lowerbound > 1:
		mid = (upperbound + lowerbound) // 2
		if verify(H, n, mid):
			lowerbound = mid
		else:
			upperbound = mid
	print(lowerbound)


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

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, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())

def sry(a):
	global lis
	global n
	ll = list(lis)[::-1]
	for i in range(len(ll) - 2):
		if ll[i] < a:
			return False
		ll[i + 2] += min(lis[n - 1 - i] // 3 * 2, (ll[i] - a) // 3 * 2)
		ll[i + 1] += min(lis[n - 1 - i] // 3, (ll[i] - a) // 3)
	for i in range(len(ll) - 2, len(ll)):
		if ll[i] < a:
			return False
	return True
for ppp in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	lo = 0
	hi = max(lis)
	while lo < hi:
		mid = lo + (hi - lo + 1) // 2
		if sry(mid):
			lo = mid
		else:
			hi = mid - 1
	print(lo)


import array
import bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType
decimal.getcontext().rounding = decimal.ROUND_HALF_UP
graphDict = collections.defaultdict
queue = collections.deque

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		to = f(*args, **kwargs)
		if stack:
			return to
		else:
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						return to
					to = stack[-1].send(to)
	return wrappedfunc

class Graphs:

	def __init__(self):
		self.graph = graphDict(set)

	def add_edge(self, u, v):
		self.graph[u].add(v)
		self.graph[v].add(u)

	def dfs_utility(self, nodes, visited_nodes, colors, parity, level):
		global count
		if nodes == 1:
			colors[nodes] = -1
		elif len(self.graph[nodes]) == 1 and parity % 2 == 0:
			if q == 1:
				colors[nodes] = 1
			else:
				colors[nodes] = -1
				count += 1
		elif parity % 2 == 0:
			colors[nodes] = -1
		else:
			colors[nodes] = 1
		visited_nodes.add(nodes)
		for neighbour in self.graph[nodes]:
			new_level = level + 1
			if neighbour not in visited_nodes:
				self.dfs_utility(neighbour, visited_nodes, colors, level - 1, new_level)

	def dfs(self, node):
		Visited = set()
		color = collections.defaultdict()
		self.dfs_utility(node, Visited, color, 0, 0)
		return color

	def bfs(self, node, f_node):
		count = float('inf')
		visited = set()
		level = 0
		if node not in visited:
			queue.append([node, level])
			visited.add(node)
		flag = 0
		while queue:
			parent = queue.popleft()
			if parent[0] == f_node:
				flag = 1
				count = min(count, parent[1])
			level = parent[1] + 1
			for item in self.graph[parent[0]]:
				if item not in visited:
					queue.append([item, level])
					visited.add(item)
		return count if flag else -1
		return False

class Tree:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def inorder(node, lis):
	if node:
		inorder(node.left, lis)
		lis.append(node.data)
		inorder(node.right, lis)
	return lis

def leaf_node_sum(root):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return root.data
	return leaf_node_sum(root.left) + leaf_node_sum(root.right)

def hight(root):
	if root is None:
		return -1
	if root.left is None and root.right is None:
		return 0
	return max(hight(root.left), hight(root.right)) + 1

class UnionFind:
	parents = []
	sizes = []
	count = 0

	def __init__(self, n):
		self.count = n
		self.parents = [i for i in range(n)]
		self.sizes = [1 for i in range(n)]

	def find(self, i):
		if self.parents[i] == i:
			return i
		else:
			self.parents[i] = self.find(self.parents[i])
			return self.parents[i]

	def unite(self, i, j):
		root_i = self.find(i)
		root_j = self.find(j)
		if root_i == root_j:
			return
		elif root_i < root_j:
			self.parents[root_j] = root_i
			self.sizes[root_i] += self.sizes[root_j]
		else:
			self.parents[root_i] = root_j
			self.sizes[root_j] += self.sizes[root_i]

	def same(self, i, j):
		return self.find(i) == self.find(j)

	def size(self, i):
		return self.sizes[self.find(i)]

	def group_count(self):
		return len(set((self.find(i) for i in range(self.count))))

	def answer(self, extra, p, q):
		dic = collections.Counter()
		for q in range(n):
			dic[self.find(q)] = self.size(q)
		hq = list(dic.values())
		heapq._heapify_max(hq)
		ans = -1
		for z in range(extra + 1):
			if hq:
				ans += heapq._heappop_max(hq)
			else:
				break
		return ans

def rounding(n):
	return int(decimal.Decimal(f'{n}').to_integral_value())

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def p_sum(array):
	return list(itertools.accumulate(array))

def base_change(nn, bb):
	if nn == 0:
		return [0]
	digits = []
	while nn:
		digits.append(int(nn % bb))
		nn //= bb
	return digits[::-1]

def diophantine(a: int, b: int, c: int):
	(d, x, y) = extended_gcd(a, b)
	r = c // d
	return (r * x, r * y)

@bootstrap
def extended_gcd(a: int, b: int):
	if b == 0:
		(d, x, y) = (a, 1, 0)
	else:
		(d, p, q) = (yield extended_gcd(b, a % b))
		x = q
		y = p - q * (a // b)
	yield (d, x, y)
BUFSIZE = 8192

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, **kwargs):
		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, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def inp():
	return sys.stdin.readline().strip()

def map_inp(v_type):
	return map(v_type, inp().split())

def list_inp(v_type):
	return list(map_inp(v_type))

def interactive():
	return sys.stdout.flush()

def valid(x):
	temp = list.copy(arr)
	flag = 1
	for i in range(n - 2):
		if flag:
			if arr[i] < x:
				return False
			(div, rem) = divmod(arr[i] - x, 3)
			temp[i] = x + rem
			temp[i + 1] += div
			temp[i + 2] += 2 * div
			flag = 0
		else:
			if temp[i] < x:
				return False
			(div, rem) = divmod(arr[i], 3)
			if temp[i] - (arr[i] - rem) >= x:
				temp[i] -= arr[i] - rem
				temp[i + 1] += div
				temp[i + 2] += 2 * div
			else:
				f = 0
				l = arr[i] + 1
				while f + 1 < l:
					m = (f + l) // 2
					(q, r) = divmod(m, 3)
					if temp[i] - (m - r) >= x:
						f = m
					else:
						l = m
				temp[i] -= f - f % 3
				temp[i + 1] += f // 3
				temp[i + 2] += 2 * (f // 3)
	if min(temp) >= x:
		return True
	else:
		return False
for _ in range(int(inp())):
	n = int(inp())
	arr = list_inp(int)
	arr.reverse()
	start = 1
	end = 10 ** 9
	while start + 1 < end:
		mid = (start + end) // 2
		if valid(mid):
			start = mid
		else:
			end = mid
	print(start)


import sys
import os.path
from collections import *
import math
import bisect
import heapq as hq
from fractions import Fraction
from random import randint
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = [int(x) for x in input().split()]
	low = min(arr)
	high = max(arr)
	res = -1
	while low <= high:
		mid = (low + high) // 2
		brr = arr.copy()
		tmp = 0
		tmp1 = 0
		z = True
		for i in range(n - 1, 1, -1):
			if brr[i] + tmp < mid:
				z = False
				break
			a = max(mid - tmp, 0)
			brr[i] -= a
			x = brr[i] // 3
			tmp = tmp1 + x
			tmp1 = 2 * x
		brr[1] += tmp
		brr[0] += tmp1
		if min(brr[1], brr[0]) < mid:
			z = False
		if z == True:
			res = mid
			low = mid + 1
		else:
			high = mid - 1
	print(res)
t = int(input())
while t:
	t -= 1
	solve()


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

def inps():
	return input().strip()

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

def insr():
	s = input().strip()
	return list(s[:len(s)])

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

def check(x):
	if l[-1] < x:
		return 0
	if min(l) >= x:
		return 1
	z = l.copy()
	ex = [0 for i in range(n)]
	ex[-1] = max(0, z[-1] - x)
	ex[-1] -= ex[-1] % 3
	val = ex[-1] // 3
	if val >= x:
		ex[-2] += z[-2]
		ex[-2] -= ex[-2] % 3
	else:
		need = x - val
		if need <= z[-2]:
			ex[-2] = max(0, z[-2] - need)
			ex[-2] -= ex[-2] % 3
		else:
			return 0
	for i in range(n - 1, 1, -1):
		val = 2 * (ex[i] // 3) + ex[i - 1] // 3
		if val >= x:
			ex[i - 2] += z[i - 2]
		else:
			need = x - val
			if need <= z[i - 2]:
				ex[i - 2] = z[i - 2] - need
				ex[i - 2] -= ex[i - 2] % 3
			else:
				return 0
	for i in range(2, n):
		z[i] -= ex[i]
		z[i - 1] += ex[i] // 3
		z[i - 2] += 2 * (ex[i] // 3)
	if min(z) < x:
		return 0
	return 1
for _ in range(inp()):
	n = inp()
	l = inlt()
	(lf, rt) = (1, 10 ** 9 + 10)
	while lf < rt - 1:
		mid = (lf + rt) // 2
		if check(mid):
			lf = mid
		else:
			rt = mid
	if check(rt):
		print(rt)
	else:
		print(lf)


def solve(n, k, a):
	ex = [0 for i in a]
	for i in range(n - 1, 1, -1):
		s = a[i] + ex[i]
		if s < k:
			return False
		sh = a[i] - max(k - ex[i], 0)
		ex[i - 1] += sh // 3
		ex[i - 2] += 2 * (sh // 3)
	return a[0] + ex[0] >= k and a[1] + ex[1] >= k
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = min(a)
	r = max(a)
	ans = l
	while r >= l:
		m = l + (r - l) // 2
		if solve(n, m, a):
			ans = max(ans, m)
			l = m + 1
		else:
			r = m - 1
	print(ans)


def solve(arr, mini):
	counter = [0, 0]
	n = len(arr)
	for i in range(n - 1, -1, -1):
		if arr[i] + counter[0] + 2 * counter[1] - mini < 0:
			return False
		ext = arr[i] + counter[0] + 2 * counter[1] - mini
		if counter[0] + 2 * counter[1] >= mini:
			ext = arr[i]
		counter[1] = counter[0]
		counter[0] = ext // 3
		if i == 1:
			counter[0] = 0
	return True
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	l = 0
	r = 10 ** 9 + 2
	while l < r - 1:
		mid = (l + r) // 2
		if solve(arr, mid):
			l = mid
		else:
			r = mid - 1
	while not solve(arr, r):
		r -= 1
	print(r)


import sys

def input():
	return sys.stdin.readline()

def isGood(avail, mn, n):
	s = [0] * n
	for i in range(n - 1, -1, -1):
		if i == 1:
			break
		if avail[i] + s[i] < mn:
			return False
		else:
			s[i - 1] += min((avail[i] + s[i] - mn) // 3, avail[i] // 3)
			s[i - 2] += min((avail[i] + s[i] - mn) // 3 * 2, avail[i] // 3 * 2)
	if s[0] + avail[0] < mn or avail[1] + s[1] < mn:
		return False
	else:
		return True

def binary_search(s, n):
	l = 1
	r = 1000000000
	while l + 1 < r:
		m = (l + r) // 2
		if isGood(s, m, n):
			l = m
		else:
			r = m
	print(l)
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	binary_search(s, n)


def check(a, m):
	tmp = a.copy()
	for i in range(n - 1, 1, -1):
		if tmp[i] < m:
			return False
		d = (tmp[i] - m) // 3
		if 3 * d > a[i]:
			d = a[i] // 3
		tmp[i - 1] += d
		tmp[i - 2] += 2 * d
	if tmp[0] < m or tmp[1] < m:
		return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(l, r) = (min(a), max(a) + 1)
	while r - l > 1:
		m = (l + r) // 2
		if check(a, m):
			l = m
		else:
			r = m
	print(l)


T = int(input())
for t in range(T):
	n = int(input())
	A = [int(i) for i in input().split()]
	lo = min(A)
	hi = max(A)

	def can(sz):
		n = len(A)
		Acp = A[:]
		for i in range(n - 1, 1, -1):
			if Acp[i] - A[i] > sz:
				max_amt_donatable = A[i]
			else:
				max_amt_donatable = max(0, Acp[i] - sz)
			d = max_amt_donatable // 3
			if i - 1 >= 0:
				Acp[i - 1] += d
			if i - 2 >= 0:
				Acp[i - 2] += 2 * d
			Acp[i] -= 3 * d
		for i in range(n):
			if Acp[i] < sz:
				return 0
		return 1
	while lo < hi:
		mid = (lo + hi + 1) // 2
		if can(mid):
			lo = mid
		else:
			hi = mid - 1
	print(lo)


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	l = 0
	r = 10 ** 9 + 10
	while r - l > 1:
		m = (l + r) // 2
		k = h.copy()
		flag = True
		for i in range(n - 1, 1, -1):
			if k[i] < m:
				flag = False
				break
			d = (k[i] - m) // 3
			if d * 3 > h[i]:
				d = h[i] // 3
			k[i - 1] += d
			k[i - 2] += 2 * d
		if k[0] < m or k[1] < m:
			flag = False
		if flag:
			l = m
		else:
			r = m
	print(l)


import sys, array, bisect, collections, heapq, itertools, math, functools
sys.setrecursionlimit(100000)

def _r():
	return sys.stdin.buffer.readline()

def rs():
	return _r().decode('ascii').strip()

def rn():
	return int(_r())

def rnt():
	return tuple(map(int, _r().split()))

def rnl():
	return list(rnt())

def rna():
	return array.array('q', rnt())

def pnl(l):
	print(' '.join(map(str, l)))

def solve(n, a):

	def _can(x):
		p = pp = 0
		for i in range(n - 1, 1, -1):
			curr = a[i] + p
			if curr < x:
				return False
			to_send = min(a[i], curr - x) // 3
			(p, pp) = (pp + to_send, 2 * to_send)
		return a[1] + p >= x and a[0] + pp >= x
	l = sol = 1
	r = max(a) + 1
	while l <= r:
		mid = l + (r - l) // 2
		if _can(mid):
			sol = mid
			l = mid + 1
		else:
			r = mid - 1
	return sol
for _ in range(rn()):
	n = rn()
	a = rnl()
	print(solve(n, a))


import sys
from collections import deque
import math
from bisect import bisect_left
from functools import cmp_to_key

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
for _ in range(II()):
	n = II()
	a = LI()
	l = 1
	r = 10 ** 9
	while l <= r:
		mid = (l + r) // 2
		d = [0 for _ in range(n)]
		boo = True
		for i in range(n - 1, -1, -1):
			if a[i] + d[i] < mid:
				boo = False
				break
			if i > 1:
				temp = min(a[i] + d[i] - mid, a[i])
				temp //= 3
				d[i - 1] += temp
				d[i - 2] += temp * 2
		if boo:
			l = mid + 1
		else:
			r = mid - 1
	print(r)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from itertools import permutations
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

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, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=(-2, -2), func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += 1
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += 1
		self.temp.data = pre_xor

	def query(self, xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = xor & 1 << i
			if not val:
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				elif self.temp.right:
					self.temp = self.temp.right
			elif self.temp.right and self.temp.right.count > 0:
				self.temp = self.temp.right
			elif self.temp.left:
				self.temp = self.temp.left
			self.temp.count -= 1
		return xor ^ self.temp.data
for ik in range(int(input())):
	n = int(input())
	e = list(map(int, input().split()))

	def find(x):
		l = e + []
		for i in range(n - 1, 1, -1):
			if l[i] < x:
				return False
			else:
				d = min((l[i] - x) // 3, e[i] // 3)
				l[i] -= 3 * d
				l[i - 1] += d
				l[i - 2] += 2 * d
		if l[0] >= x and l[1] >= x:
			return True
		return False
	st = 0
	end = max(e)
	ans = 0
	while st <= end:
		mid = (st + end) // 2
		if find(mid) == True:
			ans = mid
			st = mid + 1
		else:
			end = mid - 1
	print(ans)


import sys
input = sys.stdin.readline

def main():
	from typing import Callable

	def lastTrue(lo: int, hi: int, f: Callable[[int], bool]) -> int:
		lo -= 1
		dif = hi - lo
		while dif > 0:
			while lo + dif <= hi and f(lo + dif):
				lo += dif
			dif //= 2
		return lo

	def f(x):
		ar2 = ar.copy()
		for i in range(n - 1, 1, -1):
			if ar2[i] < x:
				return False
			d = min(ar[i] // 3, (ar2[i] - x) // 3)
			ar2[i] -= 3 * d
			ar2[i - 1] += d
			ar2[i - 2] += 2 * d
		if ar2[0] >= x and ar2[1] >= x:
			return True
		else:
			return False
	t = int(input())
	for _ in range(t):
		n = int(input())
		ar = list(map(int, input().split()))
		print(lastTrue(0, 10 ** 9 + 5, f))
main()


from sys import stdin
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
ceil_div = lambda a, b: -(-a // b)
mod = 10 ** 9 + 7
for _ in range(rn()):
	n = rn()
	h = rl()
	lo = min(h)
	hi = max(h)
	ans = lo

	def f(val, arr):
		for i in range(len(arr) - 1, 1, -1):
			if arr[i] < val:
				return False
			diff = min(arr[i] - val, h[i])
			diff -= diff % 3
			arr[i] -= diff
			arr[i - 1] += diff // 3
			arr[i - 2] += 2 * diff // 3
		return arr[0] >= val and arr[1] >= val
	while lo <= hi:
		mid = (lo + hi) // 2
		if f(mid, h.copy()):
			ans = max(ans, mid)
			lo = mid + 1
		else:
			hi = mid - 1
	print(ans)


import bisect
mod = 10 ** 9 + 7
eps = 10 ** (-9)

def __gcd(a, b):
	return a if b == 0 else __gcd(b, a % b)

def __lcm(a, b):
	return a * b / __gcd(a, b)

def __fact(n):
	return 1 if n == 1 else n * __fact(n - 1)

def __mex(a):
	mex = 0
	a.sort()
	for x in a:
		if x <= mex:
			mex += 1
		else:
			break
	return mex

def __dist(x1, y1, x2, y2):
	return (x1 - x2) ** 2 + (y1 - y2) ** 2

def __getprimes(n):
	isprime = [True for i in range(n + 1)]
	primes = []
	for i in range(2, n + 1):
		if isprime[i]:
			for j in range(i * i, n + 1, i):
				isprime[j] = False
	for i in range(2, n + 1):
		if isprime[i]:
			primes.append(i)
	return primes

def __modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def __isprime(n):
	if n < 2:
		return False
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True

def __cntprimediv(n):
	ret = 0
	x = n
	i = 2
	while i * i <= x:
		while n % i == 0:
			n //= i
			ret += 1
		i += 1
	if n > 1:
		ret += 1
	return ret

def __primefactors(n):
	ret = []
	x = n
	i = 2
	while i * i <= x:
		while n % i == 0:
			ret.append(i)
			n //= i
		i += 1
	if n > 1:
		ret.append(n)
	return ret

def __sumdigit(n):
	ret = 0
	while n > 0:
		ret += n % 10
		n //= 10
	return ret

def __zfunc(s):
	n = len(s)
	z = [0 for i in range(n)]
	l = 0
	r = 0
	for i in range(1, n):
		if r >= i:
			z[i] = min(z[i - l], r - i + 1)
		while z[i] + i < n and s[z[i]] == s[z[i] + i]:
			z[i] += 1
		if i + z[i] - 1 > r:
			l = i
			r = i + z[i] - 1
	return z

def __to(n, x):
	ret = ''
	while n > 0:
		q = n % x
		if q < 10:
			ret += str(q)
		else:
			ret += chr(q - 10 + ord('a'))
		n //= x
	return ret[::-1]

def solve(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = 1
	r = max(a) + 1
	while r - l > 1:
		m = (l + r) // 2
		ok = True
		b = [x for x in a]
		s = [0 for i in range(n)]
		for i in range(n - 1, 1, -1):
			if b[i] + s[i] < m:
				ok = False
				break
			has = (b[i] + s[i] - m) // 3
			if has * 3 > b[i]:
				has = b[i] // 3
			s[i - 1] += has
			s[i - 2] += 2 * has
		for i in range(n):
			if b[i] + s[i] < m:
				ok = False
				break
		if ok:
			l = m
		else:
			r = m
	print(l)
t = 1
t = int(input())
for i in range(t):
	solve(i + 1)


import sys
from math import factorial, gcd
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest, nsmallest
from itertools import groupby, accumulate, permutations
from copy import deepcopy
INF = float('inf')
input = sys.stdin.readline
rl = lambda : list(map(int, input().split()))
rs = lambda : sys.stdin.readline().strip()

def check(x):
	B = A[:]
	for i in range(n - 1, 1, -1):
		if B[i] < x:
			return False
		maxMove = A[i] // 3
		move = max(0, min((B[i] - x) // 3, maxMove))
		B[i] -= 3 * move
		B[i - 1] += move
		B[i - 2] += 2 * move
	return B[0] >= x and B[1] >= x
for _ in range(int(input())):
	n = int(input())
	A = rl()
	(l, r) = (min(A), max(A))
	while l < r:
		mid = r - (r - l) // 2
		if check(mid):
			l = mid
		else:
			r = mid - 1
	print(l)


import copy

def atleast(stones, x, original):
	n = len(stones)
	for i in range(n - 1, 1, -1):
		d = max(0, (stones[i] - x) // 3)
		if 3 * d > original[i]:
			d = original[i] // 3
		stones[i - 1] += d
		stones[i - 2] += 2 * d
		stones[i] -= 3 * d
	for s in stones:
		if s < x:
			return False
	return True

def solution(stones, lower, upper):
	if lower == upper:
		return lower
	mid = (lower + upper) // 2
	copied = copy.copy(stones)
	if upper == lower + 1:
		if atleast(copied, upper, stones):
			return upper
		else:
			return lower
	isPossible = atleast(copied, mid, stones)
	if isPossible:
		return solution(stones, mid, upper)
	else:
		return solution(stones, lower, mid - 1)
t = int(input())
for _ in range(t):
	n = int(input())
	stones = list(map(int, input().split()))
	print(solution(stones, 0, int(1000000000.0 + 1)))


import sys
import math
from functools import lru_cache
from heapq import heappush, heappop, heappushpop
from itertools import permutations
from operator import itemgetter, le
from collections import deque
from collections import Counter
from itertools import accumulate
from collections import defaultdict
from bisect import bisect_right as br
from bisect import bisect_left as bl
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def f(x):
	dh = [0] * n
	for i in range(2, n)[::-1]:
		if h[i] + dh[i] >= x:
			d = min(h[i] // 3, (h[i] + dh[i] - x) // 3)
			dh[i - 1] += d
			dh[i - 2] += 2 * d
		else:
			return False
	if h[0] + dh[0] >= x and h[1] + dh[1] >= x:
		return True
	return False
t = I()
for _ in range(t):
	n = I()
	h = LI()
	(ng, ok) = (10 ** 9 + 1, 0)
	while ng - ok > 1:
		mid = (ok + ng) // 2
		if f(mid):
			ok = mid
		else:
			ng = mid
	print(ok)


for i in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	l = 0
	r = 10 ** 9
	while l < r:
		a = h.copy()
		mid = (l + r + 1) // 2
		for i in range(n - 1, 1, -1):
			if a[i] < mid:
				break
			d = min(h[i], a[i] - mid) // 3
			a[i] -= 3 * d
			a[i - 1] += d
			a[i - 2] += 2 * d
		if min(a) >= mid:
			l = mid
		else:
			r = mid - 1
	print(l)


import sys
from sys import stdin
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	n = int(stdin.readline())
	h = list(map(int, stdin.readline().split()))
	l = 0
	r = max(h) + 1
	while r - l != 1:
		a = [i for i in h]
		m = (l + r) // 2
		for i in range(n - 1, -1, -1):
			if a[i] < m:
				r = m
				break
			if i >= 2:
				rem = min(h[i], a[i] - m)
				a[i - 1] += rem // 3
				a[i - 2] += rem // 3 * 2
		else:
			l = m
	ANS.append(str(l))
print('\n'.join(ANS))


def check(mid, arr, n):
	v = arr.copy()
	for i in range(n - 1, 1, -1):
		if v[i] < mid:
			return False
		x = min(arr[i], v[i] - mid) // 3
		v[i - 1] += x
		v[i - 2] += x * 2
	return v[0] >= mid and v[1] >= mid

def solve():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		l = 0
		r = max(arr)
		while l < r:
			mid = int(l + (r - l + 1) / 2)
			if check(mid, arr, n):
				l = mid
			else:
				r = mid - 1
		print(l)
solve()


import sys
import copy

def readstr():
	input = sys.stdin.readline
	a = str(input().split()[0])
	return a

def readnum():
	input = sys.stdin.readline
	a = list(map(int, input().split()))
	return a

def printf(val):
	sys.stdout.write(str(val) + '\n')

def power(a, b, mod):
	if b == 1:
		return a
	if b == 0:
		return 1
	ans = power(a, b // 2, mod)
	ans *= ans
	if b % 2:
		ans *= a
	ans = ans % mod
	return ans

def factorial(n, start=1, skip=None):
	res = start
	for i in range(1, n + 1):
		if i == skip:
			continue
		res *= i
	return res

def make_deg(l):
	deg = {}
	for i in l:
		if not i in deg:
			deg[i] = 0
		deg[i] += 1
	return deg

def get_sorted_idx(l, shift):
	tmp = sorted(range(len(l)), key=l.__getitem__)
	res = [0] * len(tmp)
	for i in range(len(tmp)):
		res[tmp[i]] = shift + i
	return res

def func(x):
	(d_prev1, d_prev2, d_prev3) = (0, 0, 0)
	for i in reversed(range(0, n)):
		arr_current = arr[i] + d_prev1 + 2 * d_prev2
		if i >= 2:
			d = min(arr[i] // 3, max(0, (arr_current - x) // 3))
		else:
			d = 0
		(d_prev2, d_prev1) = (d_prev1, d)
		if arr_current < x:
			return False
	return True

def binary_search(f, x_min, x_max):
	if x_max - x_min <= 1:
		return x_min
	x_mid = (x_max + x_min) // 2
	if f(x_mid):
		return binary_search(f, x_mid, x_max)
	else:
		return binary_search(f, x_min, x_mid)
global arr
for _ in range(readnum()[0]):
	n = readnum()[0]
	arr = readnum()
	(l, r) = (min(arr), min([arr[i] + arr[i + 1] // 3 + 2 * arr[i + 2] // 3 for i in range(n - 2)]))
	print(binary_search(func, l, r + 1))


def read_ints():
	return [int(x) for x in input().rstrip().rsplit()]

def ok(arr, k):
	test_arr = arr.copy()
	for i in range(len(arr) - 1, 1, -1):
		if test_arr[i] < k:
			return False
		d_i = min(test_arr[i] - k, arr[i])
		test_arr[i - 1] += d_i // 3
		test_arr[i - 2] += d_i // 3 * 2
	return test_arr[0] >= k and test_arr[1] >= k

def binarySearch(arr) -> int:
	bad = 1000000000
	good = 0
	while abs(bad - good) > 1:
		middle = (bad + good) // 2
		if ok(arr, middle):
			good = middle
		else:
			bad = middle
	return good
nn = int(input())
while nn > 0:
	n = int(input())
	arr = read_ints()
	print(binarySearch(arr))
	nn -= 1