# Time:  O(n^2)
# Space: O(n * d)

# A sequence of numbers is called arithmetic if it consists of at least three elements
# and if the difference between any two consecutive elements is the same.
#
# For example, these are arithmetic sequences:
#
# 1, 3, 5, 7, 9
# 7, 7, 7, 7
# 3, -1, -5, -9
# The following sequence is not arithmetic.
#
# 1, 1, 2, 5, 7
#
# A zero-indexed array A consisting of N numbers is given.
# A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk)
# such that 0 <= P0 < P1 < ... < Pk < N.
#
# A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic
# if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k >= 2.
#
# The function should return the number of arithmetic subsequence slices in the array A.
#
# The input contains N integers. Every integer is in the range of -2^31 and 2^31-1 and 0 <= N <= 1000.
# The output is guaranteed to be less than 2^31-1.
#
#
# Example:
#
# Input: [2, 4, 6, 8, 10]
#
# Output: 7
#
# Explanation:
# All arithmetic subsequence slices are:
# [2,4,6]
# [4,6,8]
# [6,8,10]
# [2,4,6,8]
# [4,6,8,10]
# [2,4,6,8,10]
# [2,6,10]

import collections


class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        # dp[i][j] means before index i(exclusive), how many elements form a arithmetic sequences with difference j
        # so i - index, j - diff. also because j -difference is unclear, so we don't know how big the 2D array we
        # should create, hence we use dp[i] = dictionary to save space

        # for test [2,4,6,8,10], i start from 1
        #   2     4      6      8       10
        #        2->1   4->1   6->1    8->1
        #               2->2   4->1    6->1
        #                      2->3    4->2
        #                              2->4

        # for ex when i = 3, we have 2->3, which means there are 3 elements have diff 2, they are {2, 4, 6}


        dp, res = [collections.defaultdict(int) for i in xrange(len(A))], 0  # bugfixed
        # i should start from 1
        for i in xrange(1, len(A)):
            for j in xrange(i):
                # we found diff, since A[j], A[i] is arithmetic with diff A[i]-A[j], so dp[i][diff] = 1
                # we found a 2-elem sequence
                diff = A[i] - A[j]
                dp[i][diff] += 1
                # if we found diff exists in dp[j], means at least we would have a 3 ele seq
                if diff in dp[j]:
                    # because of A[i]'s attendance, we can have extra dp[j][diff] seqs
                    # for ex, when i is 8, dp[8][2] = 1, at this time dp[6][2] = 2 {2,4,6}, then
                    # we would have dp[8][2] += 2 = 3, because we would have {2,4,6,8} and {4,6,8}
                    dp[i][diff] += dp[j][diff]
                    # notice we need to add dp[j][diff] instead of dp[i][diff]
                    # for ex, when i = 2, we have dp[4][2] = 1, dp[6][2] = 2, we should not +2, because
                    # when 6 comes, we would have [2,4,6], so we should + 1, dp[i][j] doesn't mean how
                    # many seq we would have at i, just means how many ele with diff j previous to i
                    # be careful about this calculation
                    res += dp[j][diff]
        return res


if __name__ == '__main__':
    print Solution().numberOfArithmeticSlices([2, 4, 6, 8, 10])
