A warehouse tracks n consecutive shifts; shift i moved a net integer count of a[i] pallets (negative means more pallets left than arrived). Given a positive integer k, find the length of the longest contiguous stretch of shifts whose net pallet change is divisible by k. If no non-empty stretch has a sum divisible by k, output 0.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the per-shift net changes in order.
Line 3: an integer k.
Output format
A single integer: the length of the longest contiguous stretch whose sum is divisible by k (0 if none exists).
Constraints
- 1 <= n <= 100000
- -1000000 <= each net change <= 1000000
- 1 <= k <= 1000000