You're given a sequence of integers, A1 A2 ... An. The sum of the sequence from Ai to Aj is called its partial sum, 1 ≤ i ≤ j ≤ N.
For example, 56 78 67 32 125 is a sequence. Then 56+78, 32, 78+67+32+125, are a subset of its partial sums, but 67+125 is not. Of course, there are also many other partial sums of the sequence.
Now, given a sequence, can you find an integer M (L ≤ M ≤ U) that divides the maximum number of partial sums of the sequence?