You have array a_1, a_2, ..., a_{n}. Segment [l, r] (1 ≤ l ≤ r ≤ n) is good if a_{i} = a_{i} - 1 + a_{i} - 2, for all i (l + 2 ≤ i ≤ r).

Let's define len([l, r]) = r - l + 1, len([l, r]) is the length of the segment [l, r]. Segment [l_1, r_1], is longer than segment [l_2, r_2], if len([l_1, r_1]) > len([l_2, r_2]).

Your task is to find a good segment of the maximum length in array a. Note that a segment of length 1 or 2 is always good.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of elements in the array. The second line contains integers: a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9).


-----Output-----

Print the length of the longest good segment in array a.


-----Examples-----
Input
10
1 2 3 5 8 13 21 34 55 89

Output
10

Input
5
1 1 1 1 1

Output
2

Difficulty: interview

Starter code:

Solutions:
n=int(input())

L=list(map(int,input().split()))

if(n==1 or n==2):
    print(n)
else:
    length=2
    i=2
    maxx=2
    while(i<n):
        if(L[i]==L[i-1]+L[i-2]):
            length+=1
        else:
            if(length>maxx):
                maxx=length
            length=2
        i+=1
    if(length>maxx):
        maxx=length
    print(maxx)


n = int(input())
A = list(map(int, input().split()))
if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    MAX_L = 2
    i1 = 0
    i2 = 1
    while i2 < n:
        CUR_L = 2
        while i2 < n - 1 and A[i1] + A[i2] == A[i2 + 1]:
            i1 += 1
            i2 += 1
            CUR_L += 1
        MAX_L = max(MAX_L, CUR_L)
        i1 += 1
        i2 += 1
    print(MAX_L)

line = input()

integers = [int(i) for i in line.split()]
n = integers[0]

line = input()
values = [int(i) for i in line.split()]

if n > 1:
    longest = 2
    cur = 2
else:
    longest = 1
    cur = 1

for i in range(len(values)-2):
    if values[i] + values[i+1] == values[i+2]:
        cur += 1
    else:
        if cur > longest:
            longest = cur
        if n > 1:
            cur = 2
        else:
            cur = 1

if cur > longest:
    longest = cur

print(longest)


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

mx = 0
ct = 0
for i in range(n-2):
    if a[i] + a[i+1] == a[i+2]:
        ct += 1
        if ct > mx: mx = ct
    else:
        ct = 0

if n <= 2:
    print(n)
else:
    print(mx + 2)



n = int(input())
s1=2
s=[1]
a = list(map(int, input().split()))
for i in range(2,n):
    if a[i] != a[i-1]+a[i-2]:
        s.append(s1)
        s1=2
    else:
        s1+=1
s.append(s1)
if n == 1:
    print(1)
else:
    print(min(max(s),n))

n = int(input())
a = list(map(int, input().split(" ")))
res = 0
num = 0
for i in range(2, len(a), 1):
    if a[i] == a[i - 1] + a[i - 2]:
        num += 1
    else:
        num = 0        
    if num > res:
        res = num        

print(min(res + 2, n))


n = int(input())
a = list(map(int,input().split()))
c = [False]*n
for i in range(2,n):
    if a[i]==a[i-1]+a[i-2]:
        c[i] = True
m = 0
j = 0
i = 2
l = 0
while i < n:
    if c[i] == False:
        if l > m:
            m = l
            j = i-l+1
        l = 0
    else:
        l+=1
    i+=1
if l != 0 and l>m:
    m = l
    j = i-l
if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    print(m+2)

n = int(input())
a = list(map(int, input().split()))
res = 0
num = 0
for i in range(2, len(a), 1):
    if a[i] == a[i - 1] + a[i - 2]:
        num += 1
    else:
        num = 0 

    if num > res:
        res = num 

print(min(res + 2, n))

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

b = 0
c = 0
for i in range(n-2):
    if a[i] + a[i+1] == a[i+2]:
        c += 1
        if c > b: b = c
    else:
        c = 0

if n <= 2:
    print(n)
else:
    print(b + 2)

3

def readln(): return tuple(map(int, input().split()))

n, = readln()
a = readln()
l = [0] * n
l[0] = 1
for _ in range(1, n):
    if _ > 1 and a[_] == a[_ - 1] + a[_ - 2]:
        l[_] = l[_ - 1] + 1
    else:
        l[_] = 2
print(max(l))


n = int(input())
num = [int(i) for i in input().split()]

ran = [2]*n
if n>2:
    for i in range(2,n):
        if num[i]==num[i-1]+num[i-2]: ran[i]=ran[i-1]+1
        else: ran[i]=2
    print(max(ran))

else: print(n)





n = int( input() )
l = [int(x) for x in input().split()]

x=0
m=0

for i in range(2, n):
	if l[i] == l[i-1]+l[i-2]:
		x+=1
	else:
		x+=2
		if x>m:
			m=x
		x=0

x+=2
if x>m:
	m=x
	x=0
			
if(n<=2):
	print(n)
else:
	print(m)


__author__ = 'Lipen'

def actions(n,a):
	lmax = 2

	if n<=2:
		return n

	i=0
	l=2
	while i<n-2:
		q=a[i]
		w=a[i+1]
		x=a[i+2]
		if x==q+w:
			l+=1
		else:
			if l>lmax:
				lmax=l
			l=2
		i+=1

	if l>lmax:
		lmax=l

	return lmax

def main():
	n = int(input())
	a = list(map(int, input().split()))

	print(actions(n,a))

def __starting_point(): main()
__starting_point()

def read_args():
    n = int(input())
    a = list(map(int, input().split()))
    return a, n


def get_good_segment_of_max_length(a, n):
    if n <= 2:
        return n
    count = 0
    current_count = 0
    for i in range(n - 2):
        if a[i] + a[i + 1] == a[i + 2]:
            current_count += 1
            if count < current_count:
                count = current_count
        else:
            current_count = 0
    return count + 2


def __starting_point():
    a, n = read_args()
    print(get_good_segment_of_max_length(a, n))
__starting_point()

n = int(input())
arr = [int(i) for i in input().split()]
myans, pre, i = 0, 0, 0
while i < n:
    if i < 2:
        pre += 1
    else:
        if arr[i-2]+arr[i-1]==arr[i]:
            pre += 1
        else:
            pre = 2
    myans = max(myans, pre)
    i += 1
print("{0}".format(myans))


n = int(input())
a = [int(i) for i in input().split()]
b = [False, False]
for i in range(2,n):
    if a[i] == a[i - 1] + a[i - 2]:
        b.append(True)
    else:
        b.append(False)
max = 0
now = 0
for i in b:
    if i:
        now += 1
    else:
        if now > max:
            max = now
        now = 0;
if now > max:
    max = now
print(min(n, max + 2))

__author__ = 'asmn'
n=int(input())
a=list(map(int,input().split()))
ans,nl=0,0
for i in range(2,n):
    if a[i]==a[i-1]+a[i-2]:
        nl+=1
        ans=max(ans,nl)
    else:
        nl=0

print(ans+min(2,n))

L = lambda: list(map(int, input().split()))
I = lambda: int(input())
n, t = I(), L()
k = s = i = 2
while i < n:
    if t[i] == t[i - 1] + t[i - 2]: s += 1
    else: k, s = max(k, s), 2
    i += 1
print(max(k, s) - int(n == 1))

n = int(input())
b = [int(x) for x in input().split()]
max = 2
if len(b) <= max:
    max = len(b)
s = 2
for i in range(2,len(b)):
    if b[i] == b[i - 1] + b[i - 2]:
        s += 1
    else:
        s = 2
    if s > max:
        max = s
print(max)
    


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

if n < 3:
  print(n)
  return

l, r = 0, 2
max_len = r - l
while r < n:
  while r < n and a[r] == a[r - 2] + a[r - 1]:
    r += 1
  max_len = max(max_len, r - l)
  l = r - 1
  r += 1

print(max_len)

import sys
import math

n = int(sys.stdin.readline())
an = [int(x) for x in (sys.stdin.readline()).split()]

if(n == 1 or n == 2):
    print(n)
    return
    
vmax = 2

r = vmax
for i in range(2, n):
    if(an[i] == (an[i - 1] + an[i - 2])):
        r += 1
    else:
        if(r > vmax):
            vmax = r
        r = 2
        
if(r > vmax):
    vmax = r
            
print(vmax)


n = int(input())
a = [int(x) for x in input().split()]
r = [x == y for x, y in zip((t + k for t, k in zip(a[:-2], a[1:-1])), a[2:])]
ans = 2
if len(a) < 3:
	print(len(a))
	return
ptr = 0
while ptr < n:
	last = ptr
	while ptr + 2 < n and r[ptr]:
		ptr += 1
	ans = max(ans, ptr - last + 2)
	ptr += 1
print(ans)


def main():
    n = int(input())
    l = list(map(int, input().split()))
    res = len(l)
    if res > 2:
        res = m = 2
        for i in range(2, n):
            if l[i] == l[i - 1] + l[i - 2]:
                m += 1
            else:
                if res < m:
                    res = m
                m = 2
        if res < m:
            res = m
    print(res)


def __starting_point():
    main()
__starting_point()

a = int(input())
if a == 1:
    print(1)
    quit()
x = list(map(int, input().split(' ')))
new = [0] * a
for i in range(2, a):
    if x[i] == x[i-1] + x[i-2]:
        new[i] = 1

streak = 0
maxstr = 2
for i in new:
    if i == 1:
        streak += 1
    else:
        
        maxstr = max(streak+2, maxstr)
        streak = 0
maxstr = max(streak+2, maxstr)
print(maxstr)


a = int(input())
if a == 1:
    print(1)
    quit()
x = list(map(int, input().split(' ')))
new = [0] * a
for i in range(2, a):
    if x[i] == x[i-1] + x[i-2]:
        new[i] = 1

streak = 0
maxstr = 2
for i in new:
    if i == 1:
        streak += 1
    else:
        
        maxstr = max(streak+2, maxstr)
        streak = 0
maxstr = max(streak+2, maxstr)
print(maxstr)