AT_past202212_n 数列と関数

For an integer sequence $ X = (X_1, X_2, \dots, X_k) $ , let us define a function $ f(X) $ as follows: - Let $ Y = (Y_1, Y_2, \dots, Y_k) $ be the sequence obtained by sorting $ X $ in ascending order. - Then, $ \displaystyle f(X) = \sum_{i=1}^{k-1}(Y_{i+1}-Y_i)^2 $ . We have an integer sequence $ A = (A_1, A_2, \dots, A_N) $ . Given $ Q $ queries in the following format, process them in order. - Given integers $ l $ and $ r $ , find $ f(B) $ , where $ B = (A_l, A_{l + 1}, \dots, A_r) $ .

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ Q $ $ \text{Query}_1 $ $ \text{Query}_2 $ $ \vdots $ $ \text{Query}_Q $ Here, $ \text{Query}_i $ denotes the $ i $ -th query. Each query is given in the following format: > $ l $ $ r $

Print $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 We have $ A = (3, 1, 4) $ . - In the $ 1 $ -st query, $ f(B) = 0 $ , because sorting $ B = (3) $ in ascending order yields $ (3) $ . - In the $ 2 $ -nd query, $ f(B) = 4 $ , because sorting $ B = (3, 1) $ in ascending order yields $ (1, 3) $ . - In the $ 3 $ -rd query, $ f(B) = 9 $ , because sorting $ B = (1, 4) $ in ascending order yields $ (1, 4) $ . - In the $ 4 $ -th query, $ f(B) = 5 $ , because sorting $ B = (3, 1, 4) $ in ascending order yields $ (1, 3, 4) $ . ### Constraints - All values in the input are integers. - $ 1