F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

DOS Card

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1212    Accepted Submission(s): 460


Problem Description
DOS is a new single-player game that Kayzin came up with. At the beginning of the game you will be given n cards in a row, each with the number of value $a_i$.

In each "matching" operation you can choose any two cards (we assume that the subscripts of these two cards are $i,j (i < j)$. **Notice that $i$ is less than $j$**), and you will get a score of $(a_i+a_j)×(a_i-a_j)$.

Kayzin will ask you $m$ times. In the k-th query, you need to select four cards from the cards with subscripts $L_k$ to $R_k$, and "match" these four cards into two pairs (i.e., two matching operations, but the subscripts of the cards selected in the two matching operations must be different from each other. That is, a card can only be matched at most once. e.g., if you select four tickets with subscripts $a$, $b$, $c$, and $d$, matching $a$ with $b$ and $c$ with $d$, or matching $a$ with $c$ and $b$ with $d$ are legal, but matching $a$ with $b$ and $b$ with $c$ is not legal), please calculate the maximum value of the sum of the two matching scores.

Note that the queries are independent of each other.
 

Input
The first line contains an integer $T(T≤100)$ . Then $T$ test cases follow. For one case,

The first line contains two integer $n$ $(4≤n≤2×10^5)$ and $m$ $(1≤m≤10^5)$ , $n$ denotes the total number of cards , $m$ denotes the number of times Kayzin queries.

The second line contains $n$ integers $a_1,a_2,…,a_n$ $(1≤a_i≤10^8)$, denotes the value of each card.

The next $m$ lines contain Kayzin's queries. The $k$th line has two numbers, $L_k$ and $R_k$ $(1≤L_k≤R_k≤n)$, the input guarantees that $R_k-L_k≥3$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2×10^5$ and the sum of $m$ over all test cases doesn't exceed $2×10^5$.
 

Output
Print $m$ integer for each case, indicating the maximum scores that can be obtained by selecting four cards (two matching pairs)
 

Sample Input
1 5 3 5 3 2 8 4 1 5 1 4 2 5
 

Sample Output
69 -34 53
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-25 03:14:10, Gzip enabled