Minimizing Total Diversity of Rearranged Subarrays

Given a sequence \(a_1, a_2, \dots, a_N\), define the diversity of a sequence as the number of distinct elements it contains. For any contiguous subarray we call its total diversity the sum of the diversities of all its subintervals. For example, the sequence \((1,1,2)\) has diversity \(2\) (since there are two distinct numbers) and its total diversity is

[ (1)+(1)+(1)+(1)+(2)+(2)=8, ]

Now, consider a query given by two indices \(l\) and \(r\). You are allowed to arbitrarily rearrange the numbers in the subarray \(a_l, a_{l+1}, \dots, a_r\). Determine the minimum possible total diversity over all subintervals of this rearranged subarray.

Note on Rearrangement: If the subarray contains several equal numbers, they naturally should be grouped together. However, if there are several distinct numbers with frequencies \(f_1, f_2, \dots, f_k\) (with \(\sum_{i=1}^k f_i=L\)), then when arranged as contiguous blocks in some order the total diversity can be computed as the sum of the "intra-block" diversities plus the contributions from intervals spanning multiple blocks. In fact, if the blocks (with frequencies \(x_0,x_1,\dots,x_{k-1}\) in the chosen order) are arranged, then the overall total diversity is

[ \text{ans} = \sum_{i=0}^{k-1} \frac{x_i(x_i+1)}{2} + \left( \frac{\Big(\sum_{i=0}^{k-1} x_i\Big)^2 - \sum_{i=0}^{k-1} x_i^2}{2} \right) + \sum_{0 \le i < j \le k-1} (j-i)x_i x_j. ]

The first term is the intra‐block contribution, the second term is the constant part of cross‐block intervals, and the last term depends on the order. It turns out that an optimal rearrangement is achieved by ordering the blocks in a balanced fashion. One method is as follows: sort the frequencies in nonincreasing order and then build an arrangement by inserting the numbers alternately at the two ends (i.e. putting the largest frequency first, then inserting the next one to the right, then the next one to the left, and so on). Computing the value of the last summation efficiently can be done in \(O(k)\) time once the balanced order is determined.

Your task is to answer \(Q\) independent queries. For each query you are given \(l\) and \(r\), and you must output the minimum achievable total diversity for the subarray \(a_l, a_{l+1}, \dots, a_r\) if its numbers are rearranged optimally.

inputFormat

The first line contains two integers \(N\) and \(Q\) — the length of the sequence and the number of queries.

The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\).

Each of the next \(Q\) lines contains two integers \(l\) and \(r\) (1-indexed), representing a query.

outputFormat

For each query, output one line with a single integer — the minimum total diversity for the rearranged subarray \(a_l, a_{l+1}, \dots, a_r\).

sample

3 1
1 1 2
1 3

8