405311: GYM101879 H Wine Production

Porto is known worldwide for its wine production. These wines are produced in the outskirts of the city and then aged in oak barrels to obtain their unique flavor. The wineries must follow strict production standards to get the seal of approval that helps with sales. To attain these very high standards, the temperatures at the vineyards are measured daily and must satisfy very specific requirements, according to studies by experts.

In order for a grape to reach optimum development, it is important to known how many different temperatures it faced during its growth and in how many days each of these temperatures were repeated. Recent studies show that the quality of the wine is deeply correlated with the following number. Consider the growth period for the grape and count, in those days, how many distinct temperatures we had, and for each temperature, how many times it was repeated in the period. We say that the grapevine has quality $$$x$$$ if we have at least $$$x$$$ distinct temperatures that were repeated in $$$x$$$ days during the growth of its grapes.

Your task is to compute the quality of production of each grapevine in the vineyard. You are given the temperatures measured in $$$N$$$ days in the vineyard. Next, for each one of the $$$Q$$$ grapevines in the vineyard, you are given the start and end days of their growth periods. For each one of these grapevines, you must compute the maximum quality of their production.

The first line has two integers $$$N$$$ and $$$Q$$$, the number of days of temperature measurements in the vineyard and the number of grapevines, respectively. The second line has $$$N$$$ blank-separated integers. The $$$i$$$th integer is the temperature measured on day $$$i$$$. Finally, the next $$$Q$$$ lines describe each one of the grapevines. The $$$i$$$th of these lines has two integers, $$$\ell_i$$$ and $$$r_i$$$, the starting and ending day of growth of the grapes in the $$$i$$$th grapevine.

Constraints

• $$$1 \leq N, Q \leq 3 \cdot 10^4$$$
• The temperature each day is between $$$-10^9$$$ and $$$10^9$$$
• $$$1 \leq \ell_i \leq r_i \leq N$$$

Print $$$Q$$$ lines, the $$$i$$$th of which is the maximum quality of grapevine $$$i$$$.

6 3
1 2 3 1 2 1
1 6
2 4
1 5

2   


1   


2   

In the first grapevine we had 3 distinct temperatures. Only one gets repeated at least three times and two of them are repeated twice, so the maximum quality of the grapevine is $$$2$$$.

In the second grapevine the temperatures were all distinct, so the maximum quality is $$$1$$$. Finally, the maximum quality of the third grapevine is 2, since we had two temperatures that were repeated twice.