Alice and Queries
Tag(s):

BIT, Data Structures, Easy, Implementation, Segment Trees, Sorting

Problem
Editorial
Analytics

Alice is having an array of N numbers (1-based indexing) and was playing with it by answering queries of the form $L,R$ where $1 \le L \le R \le N$. Query was simply sum of elements of the array with indexes from $L to R$ (Both inclusive).

In the mean time John, her younger brother came and rearrange all the elements of the array before she could reply to the queries.

Now if earlier the output of queries were $Q[1],Q[2]...$ Now it becomes $Q'[1],Q'[2]...$

The values of $Q'[1],Q'[2]...$ may still be same. But one thing good happen in all this incidence is the sum of all the queries become maximum that is $Q'[1]+Q'[2]+...$ is maximum . She is interested in finding this maximum value of sum.

Input Format:
First line consists of N integers and each q queries. Next line contains N elements presented in array. After this, the line consists of q queries, where each query is of form $L,R$.

Output Format:
We need to find the maximum sum of query replies after the array elements are rearranged .

Constraints :

$1 \le N \le 10^{5}$ $1 \le q \le 10^{5}$

Each array element is in range between $1 to 2·10^{5}$

Each query satisfies $1 \le L \le R \le N$

SAMPLE INPUT
3 3
6 4 3
1 2
2 3
1 3

SAMPLE OUTPUT
32

Explanation

We can see that if we rearrange the elements as [3 6 4] then we get total of [9+10+13] = 32

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...