One tradition of welcoming the New Year is launching fireworks into the sky. Usually a launched firework flies vertically upward for some period of time, then explodes, splitting into several parts flying in different directions. Sometimes those parts also explode after some period of time, splitting into even more parts, and so on.

Limak, who lives in an infinite grid, has a single firework. The behaviour of the firework is described with a recursion depth n and a duration for each level of recursion t_1, t_2, ..., t_{n}. Once Limak launches the firework in some cell, the firework starts moving upward. After covering t_1 cells (including the starting cell), it explodes and splits into two parts, each moving in the direction changed by 45 degrees (see the pictures below for clarification). So, one part moves in the top-left direction, while the other one moves in the top-right direction. Each part explodes again after covering t_2 cells, splitting into two parts moving in directions again changed by 45 degrees. The process continues till the n-th level of recursion, when all 2^{n} - 1 existing parts explode and disappear without creating new parts. After a few levels of recursion, it's possible that some parts will be at the same place and at the same time — it is allowed and such parts do not crash.

Before launching the firework, Limak must make sure that nobody stands in cells which will be visited at least once by the firework. Can you count the number of those cells?


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 30) — the total depth of the recursion.

The second line contains n integers t_1, t_2, ..., t_{n} (1 ≤ t_{i} ≤ 5). On the i-th level each of 2^{i} - 1 parts will cover t_{i} cells before exploding.


-----Output-----

Print one integer, denoting the number of cells which will be visited at least once by any part of the firework.


-----Examples-----
Input
4
4 2 2 3

Output
39

Input
6
1 1 1 1 1 3

Output
85

Input
1
3

Output
3



-----Note-----

For the first sample, the drawings below show the situation after each level of recursion. Limak launched the firework from the bottom-most red cell. It covered t_1 = 4 cells (marked red), exploded and divided into two parts (their further movement is marked green). All explosions are marked with an 'X' character. On the last drawing, there are 4 red, 4 green, 8 orange and 23 pink cells. So, the total number of visited cells is 4 + 4 + 8 + 23 = 39.

 [Image] 

For the second sample, the drawings below show the situation after levels 4, 5 and 6. The middle drawing shows directions of all parts that will move in the next level.

 [Image]

Difficulty: HARD
Tags: Graph traversal

Implementation

Complete search

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Complete search

Starter code:

Solutions:
from collections import defaultdict
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [1, 1, 0, -1, -1, -1, 0, 1]
visited = defaultdict(lambda : False)
grid = [[False for _ in range(320)] for _ in range(320)]

def dfs(x, y, d, n, N, inp):
	if n >= N or visited[x, y, d, n]:
		return
	visited[x, y, d, n] = True
	dist = inp[n]
	for i in range(1, dist + 1):
		grid[x + dx[d] * i][y + i * dy[d]] = True
	if n < N:
		dfs(x + dx[d] * dist, y + dy[d] * dist, (d + 1) % 8, n + 1, N, inp)
		dfs(x + dx[d] * dist, y + dy[d] * dist, (d + 7) % 8, n + 1, N, inp)
N = int(input())
inp = list(map(int, input().strip().split()))
dfs(160, 160, 0, 0, N, inp)
result = sum(map(sum, grid))
print(result)


dr = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]
n = int(input())
t = [int(i) for i in input().split()]
visited = set()
N = 150 * 2 + 10
covers = [[0] * N for i in range(N)]

def dfs(d, pos, path):
	mem = (d, pos, path)
	if mem in visited:
		return set()
	else:
		visited.add(mem)
	if d == n + 1:
		return
	for _ in range(t[d - 1]):
		pos = (pos[0] + dr[path][0], pos[1] + dr[path][1])
		covers[pos[0]][pos[1]] = 1
	dfs(d + 1, pos, (path + 1) % 8)
	dfs(d + 1, pos, (path - 1) % 8)
dfs(1, (int(N / 2), int(N / 2)), 0)
print(sum([sum(i) for i in covers]))


from sys import stdin, stdout

def ri():
	return map(int, input().split())
w = 15
adding = [(0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1)]

def fill(x, y, dir, depth):
	for i in range(t[depth]):
		x += adding[dir][0]
		y += adding[dir][1]
		v[x][y] = 1

def dfs(x, y, dir, depth):
	if depth == n:
		return
	if (dir, depth) in T[x][y]:
		return
	fill(x, y, dir, depth)
	ndepth = depth + 1
	nx = x + adding[dir][0] * t[depth]
	ny = y + adding[dir][1] * t[depth]
	ndir = (dir + 1) % 8
	dfs(nx, ny, ndir, ndepth)
	ndir = (8 + dir - 1) % 8
	dfs(nx, ny, ndir, ndepth)
	T[x][y].add(tuple((dir, depth)))
n = int(input())
t = list(ri())
v = [[0 for i in range(n * w)] for j in range(n * w)]
T = [[set() for i in range(n * w)] for j in range(n * w)]
dfs(n * w // 2, n * w // 2, 0, 0)
ans = 0
for i in range(n * w):
	for j in range(n * w):
		if v[i][j]:
			ans += 1
print(ans)


import sys
plane = set()
crackers = {((0, -1), (0, 1))}
n = int(input())
a = [int(x) for x in input().split()]
crack_dict = {(1, 0): ((1, -1), (1, 1)), (1, 1): ((1, 0), (0, 1)), (0, 1): ((1, 1), (-1, 1)), (-1, 1): ((0, 1), (-1, 0)), (-1, 0): ((-1, 1), (-1, -1)), (-1, -1): ((-1, 0), (0, -1)), (0, -1): ((-1, -1), (1, -1)), (1, -1): ((0, -1), (1, 0))}

def move(cracker):
	(point, direc) = cracker
	point2 = (point[0] + direc[0], point[1] + direc[1])
	return (point2, direc)

def crack(cracker):
	(point, direc) = cracker
	(direc1, direc2) = crack_dict[direc]
	return ((point, direc1), (point, direc2))
for x in a:
	for i in range(x):
		crackers = set((move(cracker) for cracker in crackers))
		plane.update((cracker[0] for cracker in crackers))
	new_crackers = set()
	for cracker in crackers:
		new_crackers.update(crack(cracker))
	crackers = new_crackers
print(len(plane))


from math import sin

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

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

def pt(x):
	print(x)

def ip():
	return input()

def it():
	return int(input())

def sl(x):
	return [t for t in x]

def spl(x):
	return x.split()

def aj(liste, item):
	liste.append(item)

def bin(x):
	return '{0:b}'.format(x)

def listring(l):
	return ' '.join([str(x) for x in l])

def ptlist(l):
	print(' '.join([str(x) for x in l]))
n = it()
step = lt()
dict = {}

def explosion(start, s, d):
	(i, j) = start
	t = s + 1
	if d == 0:
		for k in range(j + 1, j + t):
			dict[i, k] = True
		return (((i, j + t - 1), (d + 7) % 8), ((i, j + t - 1), (d + 1) % 8))
	if d == 1:
		for k in range(1, t):
			dict[i + k, j + k] = True
		return (((i + t - 1, j + t - 1), (d + 7) % 8), ((i + t - 1, j + t - 1), (d + 1) % 8))
	if d == 2:
		for k in range(1, t):
			dict[i + k, j] = True
		return (((i + t - 1, j), (d + 7) % 8), ((i + t - 1, j), (d + 1) % 8))
	if d == 3:
		for k in range(1, t):
			dict[i + k, j - k] = True
		return (((i + t - 1, j - t + 1), (d + 7) % 8), ((i + t - 1, j - t + 1), (d + 1) % 8))
	if d == 4:
		for k in range(1, t):
			dict[i, j - k] = True
		return (((i, j - t + 1), (d + 7) % 8), ((i, j - t + 1), (d + 1) % 8))
	if d == 5:
		for k in range(1, t):
			dict[i - k, j - k] = True
		return (((i - t + 1, j - t + 1), (d + 7) % 8), ((i - t + 1, j - t + 1), (d + 1) % 8))
	if d == 6:
		for k in range(1, t):
			dict[i - k, j] = True
		return (((i - t + 1, j), (d + 7) % 8), ((i - t + 1, j), (d + 1) % 8))
	if d == 7:
		for k in range(1, t):
			dict[i - k, j + k] = True
		return (((i - t + 1, j + t - 1), (d + 7) % 8), ((i - t + 1, j + t - 1), (d + 1) % 8))
start = [((0, 0), 0)]
for i in range(n):
	l = []
	for (p, q) in start:
		(a, b) = explosion(p, step[i], q)
		l.append(a)
		l.append(b)
	start = set(l)
pt(len(dict))


import time
coord = set()
flows = int(input())
start = time.time()
t = list(map(int, input().split()))
directions = {0: (0, 1), 1: (1, 1), 2: (1, 0), 3: (1, -1), 4: (0, -1), 5: (-1, -1), 6: (-1, 0), 7: (-1, 1)}
was = [[[[0 for j in range(300)] for i in range(300)] for x in range(31)] for y in range(8)]

def flight(n, x=0, y=0, direction=0):
	if was[direction][n][x][y]:
		return
	was[direction][n][x][y] = 1
	if n:
		for _ in range(t[flows - n]):
			x += directions[direction][0]
			y += directions[direction][1]
			coord.add((x, y))
		flight(n - 1, x, y, (direction + 1) % 8)
		flight(n - 1, x, y, (direction - 1) % 8)
flight(flows)
print(len(coord))


from sys import *
T = int(stdin.readline())
t = [int(s) for s in stdin.readline().split(' ')]
a = []
for i in range(T - 1, -1, -1):
	if i % 2 == 0:
		a += [(e[0], -e[1]) for e in a]
		a = [(e[0] - t[i], e[1]) for e in a]
		a += [(-x - 1, 0) for x in range(t[i])]
		a = list(set(a))
	if i % 2 == 1:
		a += [(e[1], -e[0]) for e in a]
		a = [(e[0] - t[i], e[1] + t[i]) for e in a]
		a += [(-x - 1, x + 1) for x in range(t[i])]
		a = list(set(a))
print(len(a))


k = int(input()) & 1
p = []
s = range(1, 6)
for q in map(int, input().split()[::-1]):
	if k:
		p += [(x, -y) for (x, y) in p]
		p = [(x - q, y) for (x, y) in p]
		p += [(-x, 0) for x in s[:q]]
	else:
		p += [(y, -x) for (x, y) in p]
		p = [(x - q, y + q) for (x, y) in p]
		p += [(-x, x) for x in s[:q]]
	p = list(set(p))
	k = 1 - k
print(len(p))