<p>Given an integer array <code>nums</code>, return <em>the number of all the <strong>arithmetic subsequences</strong> of</em> <code>nums</code>.</p>

<p>A sequence of numbers is called arithmetic if it consists of <strong>at least three elements</strong> and if the difference between any two consecutive elements is the same.</p>

<ul>
	<li>For example, <code>[1, 3, 5, 7, 9]</code>, <code>[7, 7, 7, 7]</code>, and <code>[3, -1, -5, -9]</code> are arithmetic sequences.</li>
	<li>For example, <code>[1, 1, 2, 5, 7]</code> is not an arithmetic sequence.</li>
</ul>

<p>A <strong>subsequence</strong> of an array is a sequence that can be formed by removing some elements (possibly none) of the array.</p>

<ul>
	<li>For example, <code>[2,5,10]</code> is a subsequence of <code>[1,2,1,<strong><u>2</u></strong>,4,1,<u><strong>5</strong></u>,<u><strong>10</strong></u>]</code>.</li>
</ul>

<p>The test cases are generated so that the answer fits in <strong>32-bit</strong> integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,4,6,8,10]
<strong>Output:</strong> 7
<strong>Explanation:</strong> 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]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [7,7,7,7,7]
<strong>Output:</strong> 16
<strong>Explanation:</strong> Any subsequence of this array is arithmetic.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1&nbsp; &lt;= nums.length &lt;= 1000</code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

#define ll long long int
class Solution {
public:
    // int fun(vector<int> &nums, ll ind, ll diff, int cnt, int prev)
    // {
    //     int n = nums.size();
    //     if(ind == n)
    //     {
    //         if(cnt >= 3)
    //         return 1;
    //         else
    //         return 0;
    //     }
    //     int take = 0, notTake = 0;
    //     if(prev == LLONG_MAX || diff == LLONG_MAX || nums[ind] - prev ==
    //     diff)
    //     {
    //         if(diff == LLONG_MAX && cnt == 1)
    //         diff = nums[ind] - prev;
    //         take = 1 + fun(nums, ind + 1, diff, cnt + 1, nums[ind]);
    //     }
    //     notTake = fun(nums, ind + 1, diff, cnt, prev);
    //     return take + notTake;
    // }
    int dp[1001][1001][2];
    int FindNextIndex(vector<int> curr, int n, int j) {
        int reqIndex = n;
        int pos = upper_bound(curr.begin(), curr.end(), j) - curr.begin();
        if (pos != curr.size()) {
            reqIndex = curr[pos];
        }
        return reqIndex;
    }
    int rec(int index, int last, map<long long, vector<int>>& EleIndex,vector<int>& nums, int n, int flag) {
        if (index == n) {
            return flag == 0 ? 0 : 1;
        }
        if(dp[index][last][flag]!=-1){
            return dp[index][last][flag];
        }
        int NotTake = rec(FindNextIndex(EleIndex[nums[index]], n, index), last,EleIndex, nums, n, flag);
        int Take=rec(FindNextIndex(EleIndex[(long long)nums[index]+nums[index]-nums[last]], n, index), index,EleIndex, nums, n, 1);
        return dp[index][last][flag]=(int)Take+NotTake;

    }
    int numberOfArithmeticSlices(vector<int>& nums) {
        // return fun(nums, 0, LLONG_MAX, 0, LLONG_MAX);
        map<long long, vector<int>> EleIndex;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int currEle = nums[i];
            EleIndex[currEle].push_back(i); // Storing Indexes of every element
        }
        memset(dp, -1, sizeof(dp));
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // fixing two start indexes of ap
                int first = nums[i];
                int second = nums[j];
                ll diff = (ll)second - first;
                long long req = (long long)second + diff;
                int reqIndex = n;
                vector<int> curr = EleIndex[req];
                int pos = upper_bound(curr.begin(), curr.end(), j) -
                          curr.begin();
                if (pos != curr.size()) {
                    reqIndex = curr[pos];
                }
                if (reqIndex != n) {
                    int add = rec(reqIndex, j, EleIndex, nums, n, 0);
                    ans+=(int)add;
                }
            }
        }
        return ans;
    }
};
179991