Hash Table: Longest Chain

Hash Table: how long is the longest chain (worst-case lookup)

Using hash(key) = key % B to place n keys into buckets, print the length of the longest chain.

This is separate chaining's worst-case lookup cost (2521 24T2 Q7): finding a key on the longest chain needs that many comparisons. The longer the chain, the closer to O(n).

Complete it: count each bucket's chain length and print the maximum.

Hint: count chain lengths as in the previous task, then take the max. An empty table (n=0) has a longest chain of 0.

Input

• Line 1: B n.
• Line 2: n non-negative keys.

Output

• One line: the length of the longest chain.

Example: input 7 6 / 8 15 22 5 3 17 -> 3 (bucket 1 holds 8, 15, 22 — the longest chain).