题目描述

有一天，dch去烫头了，恰巧lgp是dch的理发师，如果dch回答不上lgb的问题，lgp就会给dch剃一个光头，现在dch认为题目太简单了，以他的实力这是在侮辱他，他并不想做，但是他将要变成光头了！！！！请你帮帮他。

现在给你一个长度为n的数组a,定义a[ i ]到a[ j ]的区间值为S(i , j),S(i , j) = sqrt( (a[ i ] - a[ j ]) * (a[ i ] - a[ j ]) + (i - j) * (i - j) )并且S(i , j) = S(i , k)+S(k , j) (sqrt表示平方根) 。

输入两个数x，y，求S(x , y)的最小值。

输入格式

第一行两个数n,m。

第二行有n个数，第i个数代表a i 。

接下来m行，每行两个数x , y。（x < y）

输出格式

输出有m行，对应m个S(x , y）。

样例

####输入样例 1

5 2
1 5 2 4 3
0 3
1 4

输出样例 1

4.243
3.606