# https://leetcode.com/problems/length-of-longest-fibonacci-subsequence

from typing import Dict, List, Tuple

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        indexes: Dict[int, int] = {num: i for i, num in enumerate(arr)}
        d: Dict[Tuple[int, int], int] = {}
        result = 0

        for i in range(len(arr)):
            for j in range(i):
                k = indexes.get(arr[i] - arr[j])
                if k is not None and k < j:
                    d[j, i] = d.get((k, j), 2) + 1
                    result = max(result, d[j, i])
        return result