BEATS 100% SC and TC; O(n * max end element of the largest non-increasing sequence) approach
Intuition\nThe intuition is to first compute such a given pair if possible so that the given constraints are met and the value of non-decreasing array is always
# Intuition\nThe intuition is to first compute such a given pair if possible so that the given constraints are met and the value of non-decreasing array is always maximized. If no such configuration exists, then it is not possible to even have a single answer and we get the answer as 0.\n\nOtherwise, we can be sure that the difference between any two possible configuration of non-decreasing array cannot be more than the last element of the max-possible non-decreasing array.\nHence we apply dp for `ni[n - 1]` size array with to compute the prior.\n\n# Complexity\n- Time complexity:\nO(n * (ni[n - 1])), where ni[n - 1] is the max value of the end element of the largest non-increasing sequence possible.\n\n- Space complexity:\nO(ni[n - 1])\n\n# Code\n```\nclass Solution {\npublic:\n    int countOfPairs(vector<int>& a) {\n        const unsigned int n = a.size(), MOD = 1e9 + 7;\n        long long ans = 1;\n        int possible = 1;\n        vector nd(a.size(), int{}), ni(a.size(), int{INT_MAX});\n        ni[0] = a[0];\n        for (int i = 1; i < n; ++i) {\n            if (a[i] - nd[i - 1] < 0) { possible = 0; break; }\n            ni[i] = min(ni[i - 1], a[i] - nd[i - 1]);\n            nd[i] = a[i] - ni[i];\n        }\n        if (!possible) return 0;\n        /*\n        for (int i = 0; i < n; ++i) {\n            cout << nd[i] << \' \';\n        } cout << \'\\n\';\n        for (int i = 0; i < n; ++i) {\n            cout << ni[i] << \' \';\n        } cout << \'\\n\';\n        */\n        vector<unsigned int> res(ni[n - 1] + 1);\n        for (int i = 0; i <= ni[n - 1]; ++i) {\n            res[i] = i + 1;\n        }\n        for (int i = 0; i < n - 1; ++i) {\n            for (int j = 1; j <= ni[n - 1]; ++j) {\n                res[j] += res[j - 1];\n                if (res[j] >= MOD) res[j] -= MOD;\n            }\n        }\n        return res[ni[n - 1]];\n    }\n};\n```
['Dynamic Programming', 'Greedy', 'C++']