The Harmonious Sequence
Aadya is an aspiring musician who loves sequences. She's particularly fond of sequences where the sum of elements is divisible by a certain number, k. She has a sequence of n integers, a_1, a_2, ..., a_n. She wants to find the longest contiguous subsegment of this sequence such that the sum of its elements is divisible by k. A contiguous subsegment is defined by a starting index i and an ending index j (1 <= i <= j <= n). Help Aadya find the maximum possible length (j - i + 1) of such a subsegment.
Input
The first line contains two integers n and k, separated by a space. The second line contains n integers a_1, a_2, ..., a_n, separated by spaces.
Output
Print a single integer: the maximum length of a contiguous subsegment whose sum is divisible by k. If no such subsegment exists, print 0.
Constraints
1 <= n <= 200000 1 <= k <= 200000 1 <= a_i <= 10^9
Example 1
5 3 1 2 3 4 5
5
The subsegment [1, 2, 3] has sum 6, which is divisible by 3. Its length is 3. The subsegment [3] has sum 3, divisible by 3, length 1. The subsegment [4, 5] has sum 9, divisible by 3, length 2. The subsegment [1, 2, 3, 4, 5] has sum 15, divisible by 3, length 5. The longest is 5.
Example 2
6 4 2 2 2 2 2 2
6
The subsegment [2, 2] has sum 4, divisible by 4, length 2. The subsegment [2, 2, 2, 2] has sum 8, divisible by 4, length 4. The subsegment [2, 2, 2, 2, 2, 2] has sum 12, divisible by 4, length 6. The longest is 6.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 1 2 3 4 5
6 4 2 2 2 2 2 2