#2945. 神奇三角形

神奇三角形

题目描述

给定 nn 种长度的边,第 ii 种边的长度为 lil_iqq 次询问,每次给定区间 [l,r][l,r],请在 [l,r][l,r] 内找到两条边,将其组成三角形(角度不限),使得这个三角形面积最大。

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

输入格式

第一行两个正整数 n,qn,q

第二行 nn 个整数 lil_i

接下来 qq 行,每行两个整数 l,rl,r

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

2.00
7.50
10.00

提示

数据范围

下表表示数据最大值。

Subtask nn qq 特殊性质 分值
1 10510^5 r=l+1r=l+1 55
2 10001000 1515
3 10510^5 8080

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