Proficient.
Put your skills to the test.

Problem summary

Partition an array into consecutive nonempty groups, each having maximum minus minimum at most K. Count all such partitions modulo 1,000,000,007.

Constraints

1 ≤ N ≤ 10⁷; 0 ≤ A[i],K ≤ 10⁹.

Worked example

An independently prepared example for this explanation.

3 5
1 4 7

3

Solution analysis

1. Let dp[r] count valid partitions of the first r elements, with dp[0]=1. For each right endpoint r, maintain the smallest left endpoint L such that A[L…r] has range at most K. Every suffix starting at a position from L through r is then a valid final group, so dp[r+1] is the sum dp[L]+…+dp[r].
2. Two monotone queues maintain the minimum and maximum of the current window. When their difference exceeds K, advance L and discard expired indices. Store prefix sums of dp so the transition sum is obtained in constant time after the window is adjusted.
3. For A=[1,4,7],K=5, the full three-element group is invalid but either adjacent pair is valid. The three partitions are [1]|[4]|[7], [1,4]|[7], and [1]|[4,7]. Every index is added to and removed from each queue at most once, so even ten million elements are processed linearly.

Why it works

When a window is invalid, extending it left cannot repair its range; removing left elements eventually finds exactly the earliest valid start. Every valid partition of a prefix has one unique final group. Its starting position lies exactly in the maintained valid-start interval, and its preceding prefix has dp[start] possible partitions. The recurrence therefore counts every partition once. Prefix sums and monotone queues evaluate that recurrence without changing it.

Watch out. Count the empty prefix once. Maintain maxima and minima separately and remove expired indices. The criterion is max−min, not merely the difference of adjacent values.

Judge-library solution using the official training.h; compile with its local grader. There is no main. The example uses the official local-grader input/output format.

#include"training.h"
#include<vector>
// Algorithm: Let dp[r] count valid partitions of the first r elements, with dp[0]=1.
using namespace std;
int solve(vector<int>values,int limit){
    const int mod=1000000007;
    int n=static_cast<int>(values.size());
    vector<int>minimum(n),maximum(n),prefix(n+1);
    int minHead=0;
    int minTail=0;
    int maxHead=0;
    int maxTail=0;
    int left=0;
    prefix[0]=1;
    int answer=1;
    for(int right=0;right<n;++right){
        while(minTail>minHead&&values[minimum[minTail-1]]>=values[right]){
            --minTail;
        }
        minimum[minTail++]=right;
        while(maxTail>maxHead&&values[maximum[maxTail-1]]<=values[right]){
            --maxTail;
        }
        maximum[maxTail++]=right;
        while(values[maximum[maxHead]]-values[minimum[minHead]]>limit){
            if(minimum[minHead]==left){
                ++minHead;
            }
            if(maximum[maxHead]==left){
                ++maxHead;
            }
            ++left;
        }
        answer=prefix[right];
        if(left>0){
            answer=(answer-prefix[left-1]+mod)%mod;
        }
        prefix[right+1]=(prefix[right]+answer)%mod;
    }
    return answer;
}