Find the longest contiguous subsequence such that its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$ You are given $N$ $(1 \le N \le 10^6)$ positive integers $a_1, a_2, \ldots, a_N (1 \le a_i \le 10^6)$
and two positive integers $D$ $(1 \le D \le 10^6)$ and $M$ $(1 \le M \le 10^6)$

Find the longest contiguous subsequence such that 


its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$, and
$(a_i + a_{i+1} + \cdots + a_j) \le D\cdot M$.


I can find the longest contiguous subsequence such that its sum is divisible by $D$, but I don't know how to include the second condition. Can anyone help me to solve this problem? I think it should work in something like $O(N)$ or $O(N \cdot \log N)$.

To find the longest contiguous subsequence such that its sum is divisible by $D$, I use the fact that $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$ if and only if $(a_1 + a_2 + \cdots + a_{i-1}) \mod D = (a_1 + a_2 + \cdots + a_j) \mod D$. So, I calculate prefix sum and for every possible remainder I remember when it first occured.
There exists a linear time algorithm.   


Compute partial sum $s_j = \sum_{i=1}^j a_i$ and their remainders $r_j = s_j \mod D$.  
Consider the sequence $\{(j,s_j,r_j)\}_{j=0}^N$.  For each $0\leq r &lt; D$, compute the subsequence consisting of all tuple $(j,s_j,r_j)$ such that $r_j  = r$.  An easy approach is to sort the tuples in the sequence by their third component, using an stable sorting algorithm ($O(N \log N)$ time).  In this problem, $D \approx N$, so we could use bucket sort, improving the running time to linear; otherwise, using hash could also improve the running time to linear.
For each subsequence, apply the following algorithm on it.  


Pick two pointer $i,j$, both initialized as the first element in the 
subsequence.  
If $s_j - s_i &gt; DM$, point $j$ to the successor of $(j,s_j,r_j)$ in the subsequence, otherwise point $i$ to the successor of $(i,s_i,r_i)$ in the subsequence.  
Repeat step 2 until $j$ points to the last element in the sequence. 


Among all temporary values of $(i,j)$, find one that maximize $j-i$ under constraint $s_j-s_i \leq DM$.