AT_past202212_n 数列と関数

整数列 $ X = (X_1, X_2, \dots, X_k) $ に対して、関数 $ f(X) $ を以下のように定義します。 - $ X $ を昇順にソートした数列を $ Y = (Y_1, Y_2, \dots, Y_k) $ とする。 - $ \displaystyle f(X) = \sum_{i=1}^{k-1}(Y_{i+1}-Y_i)^2 $ である。 整数列 $ A = (A_1, A_2, \dots, A_N) $ があります。以下の形式のクエリが $ Q $ 個与えられるので、順に処理してください。 - 整数 $ l, r $ が与えられる。 $ B = (A_l, A_{l + 1}, \dots, A_r) $ として、 $ f(B) $ を求める。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ Q $ $ \text{Query}_1 $ $ \text{Query}_2 $ $ \vdots $ $ \text{Query}_Q $ ここで、 $ \text{Query}_i $ は $ i $ 個目のクエリを表す。各クエリは以下の形式で与えられる。 > $ l $ $ r $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 個目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ A = (3, 1, 4) $ です。 - $ 1 $ 個目のクエリでは、 $ B = (3) $ を昇順にソートすると $ (3) $ になるので、 $ f(B) = 0 $ です。 - $ 2 $ 個目のクエリでは、 $ B = (3, 1) $ を昇順にソートすると $ (1, 3) $ になるので、 $ f(B) = 4 $ です。 - $ 3 $ 個目のクエリでは、 $ B = (1, 4) $ を昇順にソートすると $ (1, 4) $ になるので、 $ f(B) = 9 $ です。 - $ 4 $ 個目のクエリでは、 $ B = (3, 1, 4) $ を昇順にソートすると $ (1, 3, 4) $ になるので、 $ f(B) = 5 $ です。 ### Constraints - 入力は全て整数 - $ 1