Longest Fibonacci Subsequence

Given a strictly increasing array of positive integers arr, a subsequence is considered Fibonacci-like if it has at least three elements and, starting from the third element, every element is the sum of the two preceding ones. In other words, for a subsequence [X₁, X₂, ..., Xₖ] (with k ≥ 3), it must hold that Xᵢ + Xᵢ₊₁ = Xᵢ₊₂ for all 1 ≤ i ≤ k-2.

Task

Implement a function that takes an array of positive integers and returns the length of the longest Fibonacci-like subsequence within the array. If no such subsequence exists, return 0.

Input

• A strictly increasing array of positive integers, arr, where 1 ≤ length of arr ≤ 1000.

Output

• An integer representing the length of the longest Fibonacci-like subsequence found in arr. If no valid Fibonacci-like subsequence exists, return 0.

Example

Input: arr = [1, 3, 4, 7, 11, 18, 29]
Output: 6

Explanation: The subsequence [3, 4, 7, 11, 18, 29] is Fibonacci-like because:
3 + 4 = 7, 4 + 7 = 11, 7 + 11 = 18, and 11 + 18 = 29.

Notes

• A subsequence does not need to occupy consecutive positions within the original array.
• Ensure that your solution is optimized for time as the array can be moderately large (up to 1000 elements).