Problem:


Score : 100 points

Problem Statement

Kode Festival is an anual contest where the hardest stone in the world is determined. (Kode is a Japanese word for "hardness".)

This year, 2^N stones participated. The hardness of the i-th stone is A_i.

In the contest, stones are thrown at each other in a knockout tournament.

When two stones with hardness X and Y are thrown at each other, the following will happen:

When X > Y:
  The stone with hardness Y will be destroyed and eliminated.
  The hardness of the stone with hardness X will become X-Y.

When X = Y:
  One of the stones will be destroyed and eliminated.
  The hardness of the other stone will remain the same.

When X < Y:
  The stone with hardness X will be destroyed and eliminated.
  The hardness of the stone with hardness Y will become Y-X.

The 2^N stones will fight in a knockout tournament as follows:

The following pairs will fight: (the 1-st stone versus the 2-nd stone), (the 3-rd stone versus the 4-th stone), ...

The following pairs will fight: (the winner of (1-st versus 2-nd) versus the winner of (3-rd versus 4-th)), (the winner of (5-th versus 6-th) versus the winner of (7-th versus 8-th)), ...

And so forth, until there is only one stone remaining.

Determine the eventual hardness of the last stone remaining.

Constraints

1 \leq N \leq 18

1 \leq A_i \leq 10^9

A_i is an integer.

Input

The input is given from Standard Input in the following format:

N
A_1
A_2
:
A_{2^N}

Output

Print the eventual hardness of the last stone remaining.

Sample Input 1

2
1
3
10
19

Sample Output 1

7

Sample Input 2

3
1
3
2
4
6
8
100
104

Sample Output 2

2



Sample input:
2
1
3
10
19


Sample output:
7

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]

while len(A) > 1:
  B = []
  i = 0
  while i < len(A):
    if A[i] == A[i+1]:
      B.append(A[i])
    else:
      B.append(abs(A[i] - A[i+1]))      
    i += 2
    A = B

print(A[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(2**N):
    A.append(int(input()))
i = 2**N
while i > 1:
    i //= 2
    for j in range(i):
        l = 2*j
        r = 2*j+1
        print(A[l], A[r])
        if A[l] < A[r]:
            A[j] = A[r]-A[l]
        elif A[l] > A[r]:
            A[j] = A[l]-A[r]
        else:
            A[j] = A[r]
print(A[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(2**N):
    A.append(int(input()))
i = 2**N
j = i // 2

while i > 1:
    i //= 2
    for j in range(i):
        l = 2*j
        r = 2*j+1
        if A[l] < A[r]:
            A[j] = A[r]-A[l]
        elif A[r] > A[l]:
            A[j] = A[l]-A[r]
        else:
            A[j] = A[r]
print(A[0])

Submission status: Wrong Answer

Solution code:
def setGroup(a):
    l = len(a)
    i = 0
    b = []
    while i < l:
        if a[i] < a[i+1]:
            b.append(a[i + 1] - a[i])
        elif  a[i] > a[i+1]:
            b.append(a[i] - a[i+1])
        else:
            b.append(a[i])
        i += 2
    return b
        
n = int(input())
i = 0
a =[]
while i < 2**n:
    a.append(int(input()))
    i += 1
while len(a) > 1:
    a = setGroup(a)
print(a)

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline().strip())

array = [None for _ in range(2**N)]
for i in range(int(2**N)):
    array[i] = int(sys.stdin.readline().strip())

for stage in range(N):
    for i in range(int(2**(N-stage-1))):
        tmp = abs(array[i*2] - array[i*2+1])
        array[i*2] = tmp if tmp != 0 else array[i*2]
        #print(array)

print(array[0])

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline().strip())

array = [None for _ in range(2**N)]
for i in range(int(2**N)):
    array[i] = int(sys.stdin.readline().strip())

for stage in range(N):
    for i in range(int(2**(N-stage-1))):
        array[i*2] = abs(array[i*2] - array[i*2+1])
        #print(array)

print(array[0])

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline().strip())

array = [None for _ in range(2**N)]
for i in range(int(2**N)):
    array[i] = int(sys.stdin.readline().strip())

for stage in range(N):
    for i in range(int(2**(N-stage-1))):
        array[i*2] = array[i*2] + array[i*2+1]
        #print(array)

print(array[0])

Submission status: Wrong Answer

Solution code:
3
1
3
2
4
6
8
100
104

Submission status: Wrong Answer

Solution code:
def battle(first, second):
    if first > second:
        return first - second
    elif first < second:
        return second - first
    else:
        return first

n = int(input())
prev = 0
for i in range(1 << (n-1)):
    first = int(input())
    second = int(input())
    new = battle(first, second)
    prev = battle(prev, new)
print(prev)
print()

Submission status: Wrong Answer

Solution code:
3
1
3
2
4
6
8
100
104

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(input())for i in range(2**n)]
while len(a)!=1:
    s,t=a.pop(0),a.pop(0)
    a.append(max(s-t,t-s))
print(a[0])

Submission status: Time Limit Exceeded

Solution code:
def battle(X, Y):
  if X==Y:
    return X
  else:
    return abs(X-Y)
N = int(input())
A = []
for i in range(2**N):
  A.append(int(input()))
for i in range(2**N-1):
  X = A.pop(0)
  Y = A.pop(0)
  A.append(battle(X, Y))
print(A[0])

Submission status: Accepted

Solution code:
n = int(input())
a = list(int(input()) for i in range(2**n))
b = []
i = 0
while n > 0:
    while i < 2**n:
        if a[i] > a[i+1]:
            b.append(a[i]-a[i+1])
        elif a[i] < a[i+1]:
            b.append(a[i+1]-a[i])
        else:
            b.append(a[i])
        i += 2
    a = list(b)
    b.clear()
    n -= 1
    i = 0
print(a[0])

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(2**N)]

while len(A) > 1:
  B = []
  i = 0
  while i+1 < len(A):
    if A[i] == A[i+1]:
      B.append(A[i])
    else:
      B.append(abs(A[i] - A[i+1]))      
    i += 2
  A = B
print(A[0])

Submission status: Accepted

Solution code:
a=[]
n=int(input())
for i in range(2**n):
    a.append(int(input()))
while len(a)>1:
    t=[]
    for i in range(0,len(a),2):
        x,y=a[i],a[i+1]
        if x==y:
            t.append(x)
        else:
            t.append(abs(x-y))
    a=t
print(*t)

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())
d=deque([])
for i in range(1<<n):
    d.append(int(input()))
for i in range(n):
    for j in range(1<<(n-1-i)):
        x=d.popleft()
        y=d.popleft()
        if x!=y:
            m=abs(x-y)
        else:
            m=x
        d.append(m)
print(d[0])

Submission status: Accepted

Solution code:
#problem3
N=int(input())
from collections import deque
#入力は2**N個からなる
d=[int(input()) for _ in range(2**N)]
def battle(x,y):
    if x!=y:
        return x+y-min(x,y)*2
    else:
        return x
d=deque(d)
for i in range(N):
    for i in range(2**(N-1-i)):
        x=d.popleft()
        y=d.popleft()
        d.append(battle(x,y))
print(d[0])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(input()) for _ in range(2**N)]
    for i in range(N):
        B = [0] * 2**(N-i-1)
        for j in range(2**(N-i-1)):
            if A[j*2] == A[j*2+1]:
                B[j] = A[j*2]
            else:
                B[j] = abs(A[j*2]-A[j*2+1])
        A = B
    print(A[0])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

K = INT()
N = 2 ** K
A = LIST(N)

while len(A) >= 2:
    tmp = []
    for i in range(len(A)//2):
        a, b = A[i*2], A[i*2+1]
        if a == b:
            tmp.append(a)
        else:
            tmp.append(abs(a - b))
    A = tmp
print(A[0])

Submission status: Accepted

Solution code:
n = int(input())
A = [int(input()) for _ in range(1<<n)]
for j in range(n):
  B = [abs(A[2*i]-A[2*i+1]) for i in range(1<<(n-1-j))]
  A = B
print(*A)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(2**N):
    a=int(input())
    A.append(a)


for i in range(N):
    B=[]
    for j in range(len(A)):
        if j%2==1:
            if A[j]==A[j-1]:
                B.append(A[j])
            else:
                B.append(abs(A[j]-A[j-1]))
    A=B
print(A[0])

Submission status: Accepted

Solution code:
# 配列に入れて、2周目は2ずつ、3周目は2^2ずつ...と飛ばしながら見ていく
N=int(input())
stone=[0]*(2**N)
for i in range(2**N):
  stone[i]=int(input())
  
for i in range(N):
  for j in range(0,2**N,(2**i)*2):
    s1=stone[j]
    s2=stone[j+(2**i)]
    if s1!=s2:
      stone[j]=abs(s1-s2)
print(stone[0])

Submission status: Accepted

Solution code:
n = int(input())
A = [int(input()) for _ in range(2 ** n)]
B = A[:]
while len(B) > 1:
  C = [0] * (len(B) // 2)
  for i in range(len(B) // 2):
    if B[i*2] == B[i*2+1]:
      C[i] = B[i*2]
    else:
      C[i] = abs(B[i*2] - B[i*2+1])
  B = C[:]
print(B[0])

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(2 ** n)]
while len(a) > 1:
    b = []
    sz = len(a)
    for i in range(sz // 2):
        p, q = a[2 * i], a[2 * i + 1]
        if p < q:
            p, q = q, p
        b.append(p - q)
    a = b
print(a[0])

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    A = []
    for _ in range(pow(2, N)): A.append(int(input()))

    # print(A)
    while len(A) > 1:
        temp = []
        for i in range(len(A)//2):
            if A[2*i] < A[2*i+1]: temp.append(A[2*i+1] - A[2*i])
            elif A[2*i] > A[2*i+1]: temp.append(A[2*i] - A[2*i+1])
            else: temp.append(A[2*i])
        A = temp
        # print(A)
    return A[0]

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
n = int(input())
a = []
for i in range(2**n):
    a.append(int(input()))

for i in range(n):
    delta = 2**(i+1)
    half = delta // 2
    for j in range(0, 2**n, delta):
        p = a[j]; q = a[j + half]
        if p == q:
            continue
        else:
            a[j] = abs(p - q)

print(a[0])

Submission status: Accepted

Solution code:
n=int(input())
A=[int(input()) for i in range(2**n)]
for i in range(n):
  B=[]
  for j in range(2**(n-1-i)):
    if A[2*j]==A[2*j+1]:
      B.append(A[2*j])
    else:
      B.append(abs(A[2*j]-A[2*j+1]))
  A=B
print(B[0])

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input())for i in range(2**n)]
while len(a)>1:
    p=[]
    for s,t in zip(a[::2],a[1::2]):
        p.append(s if s==t else abs(s-t))
    a=p
print(a[0])

Submission status: Accepted

Solution code:
def jud(x,y):
  if x<y:
    x,y = y,x
  if x == y:
    return x
  else:
    return x-y

n = int(input())
a = [int(input()) for i in range(2**n)]
for i in range(n):
  b = [0]*2**(n-i-1)
  for j in range(0,2**(n-i),2):
    b[j//2] = jud(a[j],a[j+1])
  a = b
print(a[0])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
A = [int(input()) for _ in range(2 ** N)]

Q = deque(A)

while len(Q) > 1:
    x = Q.popleft()
    y = Q.popleft()

    if x > y:
        Q.append(x - y)
    elif x == y:
        Q.append(x)
    else:
        Q.append(y - x)

print(Q.popleft())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N = int(input())
A = np.array(sys.stdin.readlines(), dtype=np.int64)

for _ in range(N):
    left = A[::2]
    right = A[1::2]
    A = np.abs(left - right)

answer = A[0]
print(answer)

Submission status: Accepted

Solution code:

n = int(input())

stone_list = [ int(input()) for i in range(2**n) ]


for k in range(n,0,-1):
    next_stone_list = []
    for i in range(2**(k-1)):
        if stone_list[2*i] == stone_list[2*i+1]:
            next_stone_list.append(stone_list[2*i])
        else:
            next_stone_list.append(abs(stone_list[2*i] - stone_list[2*i+1]))
    stone_list = next_stone_list
print(*next_stone_list)

Submission status: Accepted

Solution code:
a=[]
n=int(input())
for i in range(2**n):
    a.append(int(input()))
while len(a)>1:
    t=[]
    for i in range(0,len(a),2):
        x,y=a[i],a[i+1]
        if x==y:
            t.append(x)
        else:
            t.append(abs(x-y))
    a=t
print(*t)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(2**N):
    A.append(int(input()))
i = 2**N
while i > 1:
    i //= 2
    for j in range(i):
        l = 2*j
        r = 2*j+1
        if A[l] < A[r]:
            A[j] = A[r]-A[l]
        elif A[l] > A[r]:
            A[j] = A[l]-A[r]
        else:
            A[j] = A[r]
print(A[0])

Submission status: Accepted

Solution code:
n = int(input())

l = []
k = 0
for i in range(2**n):
	j = int(input())
	if i % 2 !=  0:
		l.append(max(k,j) - min(k,j))
	else:
		k = j

while len(l) != 1:
	ll = []
	for i in range(len(l)):
		j = l[i]
		if i % 2 != 0:
			ll.append(max(k,j) - min(k,j))
		else:
			k = j
	l = ll[:]
print(l[0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    n = int(input())
    d = deque()

    for i in range(2 ** n):
        d.append(int(input()))

    while len(d) >= 2:
        x = d.popleft()
        y = d.popleft()
        winner = abs(x - y)
        d.append(winner)

    print(d[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

N = int(input())
As = [int(sys.stdin.readline()) for _ in range(2**N)]

for _ in range(N):
    winners = []
    for A1, A2 in zip(As[::2], As[1::2]):
        if A1 != A2:
            winners.append(abs(A1-A2))
        else:
            winners.append(A1)
    As = winners

print(As[0])

Submission status: Accepted

Solution code:
def setGroup(a):
    l = len(a)
    i = 0
    b = []
    while i < l:
        if a[i] < a[i+1]:
            b.append(a[i + 1] - a[i])
        elif  a[i] > a[i+1]:
            b.append(a[i] - a[i+1])
        else:
            b.append(a[i])
        i += 2
    return b
        
n = int(input())
i = 0
a =[]
while i < 2**n:
    a.append(int(input()))
    i += 1
while len(a) > 1:
    a = setGroup(a)
print(a[0])

Submission status: Accepted

Solution code:
from collections import deque
N = int(raw_input())
A = [int(raw_input()) for i in range(2**N)]
while N > 0:
  newA = []
  for i in range(2**(N-1)):
    stone = abs(A[i*2]-A[i*2+1])
    newA.append(stone if stone != 0 else A[i*2])
  A = newA
  N -= 1
print A[0]

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline().strip())

array = [None for _ in range(2**N)]
for i in range(int(2**N)):
    array[i] = int(sys.stdin.readline().strip())

for stage in range(N):
    for i in range(int(2**(N-stage-1))):
        tmp = abs(array[i*2] - array[i*2+1])
        array[i] = tmp if tmp != 0 else array[i*2]
        #print(array)

print(array[0])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**3
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = 2 ** I()
    a = [I() for _ in range(n)]
    while len(a) > 1:
        b = []
        for i in range(len(a)//2):
            if a[i*2] == a[i*2+1]:
                b.append(a[i*2])
            else:
                b.append(abs(a[i*2] - a[i*2+1]))
        a = b

    return a[0]


print(main())

Submission status: Accepted

Solution code:
from copy import deepcopy
n = int(input())
a = [int(input()) for i in range(2**n)]
while len(a)!=1:
	b = []
	for i in range(len(a)//2):
		if a[i*2]==a[i*2+1]: b.append(a[i*2])
		else: b.append(max(a[i*2],a[i*2+1])-min(a[i*2],a[i*2+1]))
	a = deepcopy(b)
print(a[0])

Submission status: Accepted

Solution code:
def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result

arr_data = getinputdata()

n = int(arr_data[0][0])

cnt = 2 ** n

arr = []
for i in range(1, 1 + cnt):
    
    arr.append(int(arr_data[i][0]))
    
while len(arr)>1:
    
    arr_temp = []

    for i in range(0, len(arr), 2):

        if(arr[i] < arr[i + 1]):

            arr_temp.append(arr[i+1]-arr[i])

        elif(arr[i] > arr[i + 1]):

            arr_temp.append(arr[i]-arr[i+1])
            
        else:
            
            arr_temp.append(arr[i])
            

    arr=arr_temp
    
print(arr[0])

Submission status: Accepted

Solution code:
N = int(input())
arr = [int(input()) for i in range(2**N)]
while len(arr) > 1:
    tmp = []
    for x,y in zip(arr[::2],arr[1::2]):
        tmp.append(x if x==y else abs(x-y))
    arr = tmp
print(arr[0])

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
N = int(input())
a = [ int(input()) for _ in range(2**N) ]
while len(a) != 1:
    b = []
    for tmp in range(0,len(a)-1,2):
        if a[tmp] > a[tmp+1]:
            b.append(a[tmp]-a[tmp+1])
        elif a[tmp] == a[tmp+1]:
            b.append(a[tmp])
        else:
            b.append(a[tmp+1]-a[tmp])
    a = b
print(a[0])

Submission status: Accepted

Solution code:
n = int(input())
tour = [0]*20
for i in range(1<<n):
    tmp = 0
    a = int(input())
    while tour[tmp] != 0:
        a = abs(tour[tmp]-a) if a!=tour[tmp] else a
        tour[tmp] = 0
        tmp += 1
    tour[tmp] = a
print(tour[n])

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input()) for _ in range(2**n)]
for i in range(0, n):
    for j in range(0, 2**n, 2**(i+1)):
        k = j+2**i
        if a[j] > a[k]:
            a[j] -= a[k]
        elif a[j] < a[k]:
            a[j] = a[k] - a[j]
print(a[0])

Submission status: Accepted

Solution code:
def battle(first, second):
    if first > second:
        return first - second
    elif first < second:
        return second - first
    else:
        return first

n = 1 << int(input())
a = []
for i in range(n):
    a.append(int(input()))
while True:
    if n // 2 == 0:
        break
    new = []
    for i in range(n // 2):
        new.append(battle(a[i*2], a[i*2+1]))
    a = new
    n //= 2
print(a[0])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = [ int(input()) for _ in range(2**n) ]
while len(a) != 1:
    b = []
    for i in range(0, len(a), 2):
        if a[i] == a[i+1]:
            b += [ a[i] ]
        else:
            b += [ abs(a[i] - a[i+1]) ]
    a = b
print(*a)

Submission status: Accepted

Solution code:
n=input()
A=[input()for i in[0]*2**n]
while n:A=[abs(s-t)or s for s,t in zip(A[::2],A[1::2])];n-=1
print A[0]

Submission status: Accepted

Solution code:
def battle(x, y):
    if x > y:
        return x - y
    elif x == y:
        return x
    else:
        return y - x

N = int(input())
A = [int(input()) for _ in range(2 ** N)]
for i in range(N):
    K = len(A)
    tmp = []
    for j in range(0, K, 2):
        tmp.append(battle(A[j], A[j+1]))
    A = tmp
print(A[0])

Submission status: Accepted

Solution code:
n=int(input())
arr=[]
tmp=[]
for _ in range(2**n):
    tmp.append(int(input()))
arr.append(tmp)
while len(arr[-1])>1:
    tmp=[]
    for i in range(len(arr[-1])//2):
        if arr[-1][2*i] == arr[-1][2*i+1]:
            tmp.append(arr[-1][2*i])
        else:
            tmp.append(abs(arr[-1][2*i]-arr[-1][2*i+1]))
    arr.append(tmp)
print(arr[-1][0])

Submission status: Accepted

Solution code:
def hantei(a):
    l = len(a)
    c = []
    i = 0
    while l > i:
        x = a[i]
        y = a[i + 1]
        if (x > y):
            z = x - y
            c.append(z)
        elif (x < y):
            z = y - x
            c.append(z)
        else:
            c.append(x)
        i += 2
    if (len(c) > 1):
        return hantei(c)
    else:
        return c[0]

n = 2 ** int(input())
a = []
while n > 0:
    a.append(int(input()))
    n -= 1
print(str(hantei(a)))

Submission status: Accepted

Solution code:
def solve(A):
    if(len(A) == 1):
        return A[0]
    return solve([abs(A[i]-A[i+1]) for i in range(0,len(A),2)])

n = int(input())
A = []
for i in range(2**n):
    A.append(int(input()))

print(solve(A))

Submission status: Accepted

Solution code:
N = int(raw_input())
nums = []
for i in range(2**N):
    nums.append(int(raw_input()))


for n in range(N-1, -1, -1):
    for i in range(2**n):
        if nums[2*i] < nums[2*i+1]:
            nums[i] = nums[2*i+1]-nums[2*i]
        elif nums[2*i] == nums[2*i+1]:
            nums[i] = nums[2*i]
        else:
            nums[i] = nums[2*i] - nums[2*i+1]
        
print nums[0]

Submission status: Accepted

Solution code:
N = 2**input()
A = [int(raw_input()) for _ in xrange(N)]
while N > 1:
    for i in xrange(N/2):
        if A[i*2] > A[i*2+1]:
            A[i] = A[i*2] - A[i*2+1]
        elif A[i*2] == A[i*2+1]:
            A[i] = A[i*2]
        else:
            A[i] = A[i*2+1] - A[i*2]
    N /= 2
print A[0]