该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $n$ 种长度的边，第 $i$ 种边的长度为 $l_i$，$q$ 次询问，每次给定区间 $[l,r]$，请在 $[l,r]$ 内找到两条边，将其组成三角形（角度不限），使得这个三角形面积最大。

对于每个询问，请输出三角形面积的最大值。

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个整数 $l_i$。

接下来 $q$ 行，每行两个整数 $l,r$。

输出格式

对于每个询问，输出一行一个数表示答案，保留两位小数。

样例 #1

样例输入 #1

5 3
1 4 2 5 3
1 2
3 5
2 4

样例输出 #1

2.00
7.50
10.00

提示

数据范围

下表表示数据最大值。

Subtask	$n$	$q$	特殊性质	分值
1	$10^5$		$r=l+1$	$5$
2	$1000$		无	$15$
3	$10^5$			$80$

对于 $100\%$ 的数据，$1\leq l,r\leq n,1\leq l_i\leq 10^9$，保证 $l_i$ 互不相同。