rsrams

题号：NC225364
时间限制：C/C++/Rust/Pascal 15秒，其他语言30秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

You are given an array $a_1,\dots,a_n$ of positive integers. Toilet-Ares needs to solve $q$ queries.

For each query, Toilet-Ares tells you two numbers $l, r$ , and want you to solve

$\sum\limits_{L=l}^r \sum\limits_{R=L}^r \sum\limits_{c=1}^n c\cdot \left[R-L+1<2\sum\limits_{i=L}^R [a_i=c] \right]$ .

Notes: [cond] means if the conditional expression in parentheses is true, it corresponds to [cond] = 1, otherwise it corresponds to [cond] = 0.

输入描述:

The first line contains two integers  (, ),

The second line contains  integers  (),

Each of the next  lines contains two integers  (), donating once query.

输出描述:

 lines, each line contains one integer donating the answer for each query.

示例1

输入

复制

输出

复制

6
3