Longest Stable Transaction Period

Given the daily net transaction amounts transactions and a positive integer k, find the longest contiguous interval whose sum is divisible by k. This site adds 1≤n≤100000, each transaction amount a signed int32, and 1≤k≤2147483647.

输入格式

The first line contains n and k (1≤n≤100000, 1≤k≤2147483647). The second line contains n signed int32 transaction amounts. These are the ranges supported by this site.

输出格式

Output the length of the longest contiguous interval whose sum is divisible by k; if none exists, output 0.

样例 1

输入：

7 3
2 3 1 4 1 5 9

输出：

4

样例说明

Approach

When two prefix sums have the same remainder modulo k, the sum of the contiguous interval between them is divisible by k. Scan from left to right and record the position where each remainder first appears; when a remainder appears again, update the longest length with the current position minus the earliest position. Use a positive k, and reduce negative transaction amounts modulo k in the mathematical sense.

Proof of Correctness

Let the prefix sum P[j] be the sum of the first j items. The sum of the interval (i,j] is divisible by the positive integer k if and only if P[i] and P[j] are congruent modulo k. For a fixed right end j, the earliest congruent prefix produces the longest interval; the algorithm stores the earliest index of each remainder and checks every subsequent prefix, so it never misses the optimal interval and never counts an interval that fails the divisibility condition.

Complexity

The n items are scanned once, for expected time O(n); at most n+1 remainder positions are stored, for space O(n).