365B.md (1182B)
1 Source: https://codeforces.com/problemset/problem/365/B 2 3 B. The Fibonacci Segment 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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*). 22 23 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]). 24 25 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. 26 27 Input 28 29 The first line contains a single integer *n* (1 ≤ *n* ≤ 105) — the number of elements in the array. The second line contains integers: *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ 109). 30 31 Output 32 33 Print the length of the longest good segment in array *a*. 34 35 Examples 36 37 Input 38 39 ``` 40 10 41 1 2 3 5 8 13 21 34 55 89 42 ``` 43 44 Output 45 46 ``` 47 10 48 ``` 49 50 Input 51 52 ``` 53 5 54 1 1 1 1 1 55 ``` 56 57 Output 58 59 ``` 60 2 61 ```