O(N) solution using Maths
Intuition\n Describe your first thoughts on how to solve this problem. \n\n\n\nFrom this, we can conclude that whenever an element in the main array increases, 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n![lc.png](https://assets.leetcode.com/users/images/e6acf5c5-2a1a-47ff-a3dc-854c4f814ba9_1723357795.9547896.png)\n\nFrom this, we can conclude that whenever an element in the main array increases, we must add the difference to either the increasing array or the decreasing array. However, since we cannot add it to the decreasing array, it must be added to the increasing array.\n\nSimilarly, if the element decreases, the difference must be subtracted from the decreasing array.\n\n**Bold**\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSince the elements in both arrays must be greater than or equal to 0, the last element in the decreasing array must also be greater than or equal to 0. From this condition, we can determine the minimum value of the first element in the decreasing array. The range for the first element in the decreasing array can therefore be from this minimum value up to (arr[0] - mini).\n\nThis difference, (remain = arr[0] -mini ), can be used at any index to increase the corresponding element in the increasing array and decrease the corresponding element in the decreasing array. Additionally, there\'s an option to leave the arrays unchanged. Consequently, there are \\( n+1 \\) choices for the "remain" element.\n\nUsing combinatorial mathematics, the number of possible ways to distribute the "remain" element across the arrays can be calculated using the formula \\( n + r - 1 C n - 1).\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n# Code\n```\nconst int MAX = 5e3;\nconst int MOD = 1e9 + 7;\nvector<long long> factorial(5e3), inv_factorial(5e3);\nclass Solution {\npublic:\n    Solution(){\n        precompute();\n    }\n    long long mod_pow(long long x, long long y, int mod) {\n        long long result = 1;\n        while (y > 0) {\n            if (y % 2 == 1) {\n                result = (result * x) % mod;\n            }\n            x = (x * x) % mod;\n            y /= 2;\n        }\n        return result;\n    }\n    void precompute() {\n        factorial[0] = factorial[1] = 1;\n        for (int i = 2; i < MAX; ++i) {\n            factorial[i] = (factorial[i - 1] * i) % MOD;\n        }\n        inv_factorial[MAX - 1] = mod_pow(factorial[MAX - 1], MOD - 2, MOD);\n        for (int i = MAX - 2; i >= 0; --i) {\n            inv_factorial[i] = (inv_factorial[i + 1] * (i + 1)) % MOD;\n        }\n    }\n\n    long long nCr(int n, int r) {\n        if (r > n)\n            return 0;\n        return factorial[n] * inv_factorial[r] % MOD * inv_factorial[n - r] %\n               MOD;\n    }\n\n    int countOfPairs(vector<int>& arr) {\n        \n        int mini = 0; // minimum value of first element in decreasing array\n        int n = arr.size();\n        for (int i = 1; i < n; i++) {\n            if (arr[i - 1] > arr[i]) {\n                mini += (arr[i - 1] - arr[i]);\n            }\n        }\n        int remain = arr[0] - mini;\n        if (remain < 0)\n            return 0;\n        n++; // n+1 choices\n        return nCr(n + remain - 1, n - 1);\n    }\n};\n```
['Math', 'Combinatorics', 'C++']