Given an array A[ ] denoting the time taken to complete N tasks, determine the minimum amount of time required to finish the tasks considering that you can skip any task, but skipping two consecutive tasks is forbidden.
 
Example 1:
Input:
N = 2
A[] ={10,20}
Output: 10
Explanation: we can take time of
10 units and skip 20 units time.
Ã¢â¬â¹Example 2:
Input:
N = 4
A[] = {10,5,7,10}
Output: 12
Explanation: we can skip both the
tens and pick 5 and 7 only.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function minAmount() which accepts array A[] and its size N as input parameter and returns minimum amount of time required to finish the tasks.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def minAmount(self, A, n): 
        # code here 



Solutions:
class Solution:

	def minAmount(self, A, n):
		t1 = A[0]
		t2 = 0
		for i in range(1, n):
			k = A[i] + min(t1, t2)
			f = t1
			t1 = k
			t2 = f
		return min(t1, t2)


class Solution:

	def minAmount(self, A, n):
		dp = [0] * (n + 1)
		dp[1] = A[0]
		dp[2] = A[1]
		for i in range(3, len(dp)):
			dp[i] = min(dp[i - 2] + A[i - 1], dp[i - 1] + A[i - 1])
		return min(dp[-1], dp[-2])


class Solution:

	def minAmount(self, A, n):
		ans = 1000000000.0
		if n == 1:
			return A[0]
		if n == 2:
			return min(A[0], A[1])
		inc = A[0]
		exc = 0
		for i in range(1, n):
			incTemp = A[i] + min(inc, exc)
			excTemp = inc
			inc = incTemp
			exc = excTemp
		return min(inc, exc)


class Solution:

	def minAmount(self, A, n):
		pre1 = A[0]
		pre2 = 0
		for i in range(1, n):
			temp1 = min(pre1, pre2) + A[i]
			temp2 = pre1
			pre1 = temp1
			pre2 = temp2
		return min(pre1, pre2)


class Solution:

	def minAmount(self, A, n):
		summa = sum(A)
		if n < 3:
			return summa - max(A)
		A[2] += A[0]
		for i in range(3, n):
			A[i] += max(A[i - 2], A[i - 3])
		return summa - max(A[-2:])


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def minAmount(self, arr, n):
		dp = arr.copy()
		for i in range(n - 3, -1, -1):
			dp[i] = min(dp[i] + dp[i + 2], dp[i] + dp[i + 1])
		return min(dp[0], dp[1])


class Solution:

	def minAmount(self, arr, n):
		dp = arr.copy()
		for i in range(n - 3, -1, -1):
			dp[i] = min(dp[i] + dp[i + 2], dp[i] + dp[i + 1])
		return min(dp[0], dp[1])


import math

class Solution:

	def minAmount(self, A, n):
		dp = [0]
		s = 0
		ns = A[0]
		for i in range(1, n):
			nss = ns
			nsns = ns + A[i]
			sns = s + A[i]
			dp.append(min(min(nss, nsns), sns))
			s = nss
			ns = min(nsns, sns)
		return dp[-1]


import math

class Solution:

	def minAmount(self, a, n):
		inc = a[0]
		e = 0
		for i in range(1, n):
			inc_n = a[i] + min(e, inc)
			e = inc
			inc = inc_n
		return min(e, inc)


class Solution:

	def minAmount(self, A, n):
		if n == 1:
			return 0
		if n == 2:
			return min(A)
		dp = [0 if i > 1 else A[i] for i in range(n)]
		for i in range(2, n):
			dp[i] = A[i] + min(dp[i - 1], dp[i - 2])
		return min(dp[n - 2], dp[n - 1])


class Solution:

	def minAmount(self, A, n):
		a = 0
		b = A[0]
		for i in range(1, n):
			c = min(a, b) + A[i]
			d = b
			(a, b) = (d, c)
		return min(a, b)


class Solution:

	def minAmount(self, A, n):
		inc = [-1] * n
		exc = [-1] * n
		inc[0] = A[0]
		exc[0] = 0
		for i in range(1, n):
			inc[i] = min(inc[i - 1], exc[i - 1]) + A[i]
			exc[i] = inc[i - 1]
		return min(exc[n - 1], inc[n - 1])


class Solution:

	def minAmount(self, A, n):
		if len(A) == 1:
			return A[0]
		else:
			prev_a = 0
			prev_b = A[0]
			ans = float('inf')
			for i in range(1, n):
				temp = A[i] + min(prev_b, prev_a)
				ans = min(temp, prev_b)
				prev_a = prev_b
				prev_b = temp
			return ans


class Solution:

	def minAmount(self, a, n):
		for i in range(2, n):
			a[i] = min(a[i - 2], a[i - 1]) + a[i]
		return min(a[-1], a[-2])


class Solution:

	def minAmount(self, A, n):
		excl = 0
		incl = A[0]
		for i in range(1, n):
			excl_ = excl
			excl = incl
			incl = min(incl + A[i], excl_ + A[i])
		return min(incl, excl)


class Solution:

	def minAmount(self, A, n):
		t = 0
		dp = [0 for _ in range(n)]
		dp[0] = A[0]
		dp[1] = A[1]
		for i in range(2, n):
			dp[i] = min(dp[i - 1] + A[i], dp[i - 2] + A[i])
		return min(dp[-1], dp[-2])


class Solution:

	def minAmount(self, A, n):
		incl = A[0]
		excl = 0
		for i in range(1, n):
			incl_new = A[i] + min(incl, excl)
			excl_new = incl
			incl = incl_new
			excl = excl_new
		return min(incl, excl)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.minAmount(A, n))


class Solution:

	def minAmount(self, a, n):
		inc = a[0]
		exc = 0
		for i in range(1, n):
			n_exc = inc
			n_inc = min(inc, exc) + a[i]
			inc = n_inc
			exc = n_exc
		return min(inc, exc)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.minAmount(A, n))


class Solution:

	def minAmount(self, a, n):
		if n == 0:
			return 0
		incl = a[0]
		exc = 0
		for i in range(1, n):
			ni = a[i] + min(incl, exc)
			ne = incl
			incl = ni
			exc = ne
		return min(incl, exc)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.minAmount(A, n))


class Solution:

	def minAmount(self, A, n):
		inc = A[0]
		exd = 0
		for i in range(1, n):
			ans = A[i] + min(inc, exd)
			exd = inc
			inc = ans
		return min(inc, exd)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.minAmount(A, n))


class Solution:

	def minAmount(self, A, n):
		if n <= 0:
			return 0
		incl = A[0]
		excl = 0
		for i in range(1, n):
			new_incl = A[i] + min(incl, excl)
			new_excl = incl
			incl = new_incl
			excl = new_excl
		return min(incl, excl)


class Solution:

	def minAmount(self, a, n):
		inc = a[0]
		exc = 0
		for i in range(1, n):
			inc_new = a[i] + min(inc, exc)
			exc_new = inc
			inc = inc_new
			exc = exc_new
		return min(inc, exc)


class Solution:

	def minAmount(self, A, n):
		(skip, take) = (0, A[0])
		total = 0
		for i in range(1, n):
			(s, t) = (skip, take)
			skip = t
			take = min(s, t) + A[i]
			total = min(skip, take)
		return total


class Solution:

	def minAmount(self, arr, n):
		if n <= 0:
			return 0
		incl = arr[0]
		excl = 0
		for i in range(1, n):
			incl_new = arr[i] + min(excl, incl)
			excl_new = incl
			incl = incl_new
			excl = excl_new
		return min(incl, excl)


class Solution:

	def minAmount(self, A, n):
		total_time = [0, 0]
		for task_time in A:
			skip = total_time[1]
			doing = min(total_time) + task_time
			total_time = [skip, doing]
		return min(total_time)


class Solution:

	def minAmount(self, A, n):
		(not_taken, taken) = (0, A[0])
		for i in range(1, n):
			new_taken = min(A[i] + not_taken, A[i] + taken)
			not_taken = taken
			taken = new_taken
		return min(taken, not_taken)


class Solution:

	def minAmount(self, A, n):
		skip = 0
		doIt = A[n - 1]
		for i in range(n - 2, -1, -1):
			old = skip
			skip = doIt
			doIt = A[i] + min(old, doIt)
		return min(skip, doIt)


class Solution:

	def minAmount(self, A, n):
		skipped = 0
		a = A[n - 1]
		for i in range(n - 2, -1, -1):
			prev = skipped
			skipped = a
			a = A[i] + min(prev, a)
		return min(skipped, a)


class Solution:

	def minAmount(self, arr, n):
		incl = [0] * (n + 1)
		excl = [0] * (n + 1)
		incl[0] = 0
		minT = [0] * (n + 1)
		excl[0] = 0
		minT[0] = 0
		for i in range(1, n + 1):
			incl[i] = arr[i - 1] + min(incl[i - 1], excl[i - 1])
			excl[i] = incl[i - 1]
			minT[i] = min(incl[i], excl[i])
		return minT[n]


class Solution:

	def minAmount(self, A, n):
		with_skip = 0
		without_skip = A[0]
		for i in range(1, len(A)):
			temp1 = with_skip
			with_skip = without_skip
			without_skip = A[i] + min(temp1, without_skip)
		return min(with_skip, without_skip)


class Solution:

	def minAmount(self, A, n):
		a = 0
		b = A[0]
		i = 1
		while i < n:
			c = A[i] + min(a, b)
			(a, b) = (b, c)
			i += 1
		return min(a, b)


class Solution:

	def minAmount(self, A, n):
		if n == 1:
			return A[0]
		if n == 2:
			return min(A[0], A[1])
		skip = 0
		cts = A[0]
		for i in range(1, n):
			temp = skip
			skip = cts
			cts = A[i] + min(temp, cts)
		return min(skip, cts)


def Task(arr, i=0, taken=True):
	global mod
	global dp
	try:
		return dp[i, taken]
	except:
		pass
	if i == len(arr) - 2:
		if taken == True:
			return min(arr[i], arr[i + 1])
		return arr[i]
	if taken == False:
		dp[i, taken] = arr[i] + Task(arr, i + 1, True) % mod
		return dp[i, taken]
	k1 = Task(arr, i + 1, False) % mod
	k2 = arr[i] + Task(arr, i + 1, True) % mod
	dp[i, taken] = min(k1, k2) % mod
	return dp[i, taken]

def TaskTabulation(arr):
	dp = [[0 for i in range(len(arr))] for j in range(2)]
	dp[0][-1] = arr[-1]
	dp[1][-1] = 0
	dp[0][-2] = min(arr[-2], arr[-1])
	dp[1][-2] = arr[-2]
	res = float('inf')
	for i in range(len(arr) - 3, -1, -1):
		dp[1][i] = arr[i] + dp[0][i + 1]
		dp[0][i] = min(dp[1][i + 1], arr[i] + dp[0][i + 1])
	return min(dp[0][0], dp[1][0])

class Solution:

	def minAmount(self, A, n):
		global dp
		global mod
		mod = 1000000007
		dp = {}
		return TaskTabulation(A)


class Solution:

	def minAmount(self, A, n):
		if n == 1:
			return A[0]
		if n == 2:
			return min(A[0], A[1])
		exc = [0] * (n + 1)
		inc = [0] * (n + 1)
		inc[0] = A[0]
		exc[1] = A[0]
		inc[1] = A[1]
		for x in range(2, n):
			exc[x] = inc[x - 1]
			inc[x] = min(A[x] + exc[x - 1], A[x] + inc[x - 1])
		return min(exc[n - 1], inc[n - 1])


class Solution:

	def minAmount(self, A, n):
		if n <= 0:
			return 0
		incl = A[0]
		excl = 0
		for i in range(1, n):
			incn = A[i] + min(incl, excl)
			excn = incl
			incl = incn
			excl = excn
		return min(incl, excl)


class Solution:

	def minAmount(self, arr, n):
		(inc, exc) = (arr[0], 0)
		for i in range(1, n):
			new_inc = arr[i] + min(inc, exc)
			new_exc = inc
			inc = new_inc
			exc = new_exc
		return min(inc, exc)