Maximizing Dragon Lamp Beauty

Fenfen has n dragon lamps, where the color of the i-th lamp is given by \(a_i\). The beauty of a contiguous segment (interval) \([l,r]\) is defined as the number of distinct colors in \(a_l, a_{l+1}, \dots, a_r\), formally,

[ f(l,r)=#{a_i : l\le i\le r},. ]

Fenfen plans to go out for m days. On the i-th day, he will take the first \(x_i\) lamps (i.e. lamps numbered \(1,2,\dots,x_i\)). However, he noticed that when many lamps are put together, people only notice the number of distinct colors. Therefore, he decides to partition the sequence of \(x_i\) lamps (in their order) into exactly \(k_i\) contiguous segments so that each lamp is in exactly one segment.

The overall beauty for that day is the sum of the beauties of the segments. Help Fenfen maximize the beauty of each outing by choosing the optimal partition.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m)\) — the number of dragon lamps and the number of days, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the colors of the lamps.

Then follow \(m\) lines, each containing two integers \(x_i\) and \(k_i\) \((1 \leq x_i \leq n)\) — on the i-th day, Fenfen takes the first \(x_i\) lamps and partitions them into exactly \(k_i\) segments.

outputFormat

For each day, output a single integer — the maximum overall beauty that can be achieved for that day.

sample

5 2
1 2 1 3 2
5 2
3 2

5
3