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

Background

本题有多种做法~

Description

南将军统率着N个士兵，士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比较，计算出两个人的杀敌数差值，用这种方法一方面能鼓舞杀敌数高的人，另一方面也算是批评杀敌数低的人，起到了很好的效果。所以，南将军经常问军师小工第i号士兵到第j号士兵中，杀敌数最高的人与杀敌数最低的人之间军功差值是多少。现在，请你写一个程序，帮小工回答南将军每次的询问吧。 注意，南将军可能询问很多次。

Format

Input

只有一组测试数据 第一行是两个整数N,Q，其中N表示士兵的总数。Q表示南将军询问的次数。(1<N<=100000,1<Q<=1000000) 随后的一行有N个整数Vi(0<=Vi<100000000)，分别表示每个人的杀敌数。 再之后的Q行，每行有两个正正数m,n，表示南将军询问的是第m号士兵到第n号士兵。

Output

对于每次询问，输出第m号士兵到第n号士兵之间所有士兵杀敌数的最大值与最小值的差。

Sample 1

Input

5 2
1 2 6 9 3
1 2
2 4

Output

1
7

Limitation

1s, 1024KiB for each test case.