Profesor ジョイ, seorang pakar terkemuka dalam penelitian sejarah negara IOI, menerima sebuah buku harian yang konon ditulis oleh seorang penduduk negara IOI pada zaman dahulu. Untuk meneliti kehidupan di negara IOI pada zaman dahulu melalui buku harian ini, Profesor ジョイ memutuskan untuk menyelidiki peristiwa-peristiwa yang tercatat di dalamnya.

Buku harian ini mencatat peristiwa selama $N$ hari, tepat satu peristiwa setiap hari. Peristiwa-peristiwa tersebut dikelompokkan ke dalam beberapa jenis. Jenis peristiwa pada hari ke-$i$ ($1 \le i \le N$) dinyatakan oleh bilangan bulat $X_i$. Semakin besar nilai $X_i$, semakin besar skala peristiwa tersebut dianggap.

Profesor ジョイ memutuskan untuk menganalisis buku harian dengan cara berikut.

1. Pilih beberapa hari yang berurutan dari $N$ hari dalam buku harian sebagai periode yang akan dianalisis.
2. Definisikan tingkat kepentingan jenis peristiwa $t$ sebagai $t \times (\text{banyaknya peristiwa berjenis }t\text{ dalam periode tersebut})$.
3. Hitung tingkat kepentingan untuk semua jenis peristiwa, lalu tentukan nilai maksimumnya.

Profesor ジョイ menugaskan Anda untuk membuat program analisis. Program ini harus dapat menentukan tingkat kepentingan maksimum ketika periode yang akan dianalisis diberikan.

Tugas

Diberikan jenis peristiwa selama $N$ hari dalam buku harian dan $Q$ kueri yang masing-masing menyatakan suatu periode dalam buku harian, tulislah program yang menentukan tingkat kepentingan peristiwa maksimum untuk setiap kueri.

Masukan

Bacalah data berikut dari masukan standar.

• Baris pertama berisi bilangan bulat $N,Q$ yang dipisahkan oleh spasi. Ini menyatakan bahwa buku harian mencakup $N$ hari dan diberikan $Q$ kueri.
• Baris berikutnya berisi $N$ bilangan bulat $X_1,\ldots,X_N$ yang dipisahkan oleh spasi. $X_i$ ($1 \le i \le N$) menyatakan jenis peristiwa pada hari ke-$i$.
• Baris ke-$j$ ($1 \le j \le Q$) dari $Q$ baris berikutnya berisi bilangan bulat $A_j,B_j$ ($1 \le A_j \le B_j \le N$) yang dipisahkan oleh spasi. Ini menyatakan bahwa kueri ke-$j$ membahas periode dari hari ke-$A_j$ hingga hari ke-$B_j$.

Keluaran

Tuliskan $Q$ baris ke keluaran standar. Pada baris ke-$j$ ($1 \le j \le Q$), tuliskan sebuah bilangan bulat yang menyatakan tingkat kepentingan maksimum untuk kueri ke-$j$.

Batasan

Semua data masukan memenuhi syarat-syarat berikut.

• $1 \le N \le 100\,000$.
• $1 \le Q \le 100\,000$.
• $1 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$).

Subsoal

Subsoal 1 [5 poin]

Syarat-syarat berikut terpenuhi.

• $N \le 100$.
• $Q \le 100$.

Subsoal 2 [10 poin]

Syarat-syarat berikut terpenuhi.

• $N \le 5\,000$.
• $Q \le 5\,000$.

Subsoal 3 [25 poin]

• Tidak ada $i,j$ ($1 \le i \le Q$, $1 \le j \le Q$, $i \ne j$) yang memenuhi $A_i \le A_j \le B_j \le B_i$.

Subsoal 4 [60 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

Keluaran 1

9
8
8
16
16

Penjelasan

• Buku harian ini mencakup $5$ hari, dan jenis peristiwa yang tercatat adalah $7$, $8$, atau $9$.
• Dari hari ke-$1$ hingga hari ke-$2$, tingkat kepentingan jenis peristiwa $7$ adalah $7\times0=0$, jenis peristiwa $8$ adalah $8\times1=8$, dan jenis peristiwa $9$ adalah $9\times1=9$. Maka, nilai maksimumnya adalah $9$.
• Dari hari ke-$3$ hingga hari ke-$4$, tingkat kepentingan jenis peristiwa $7$ adalah $7\times1=7$, jenis peristiwa $8$ adalah $8\times1=8$, dan jenis peristiwa $9$ adalah $9\times0=0$. Maka, nilai maksimumnya adalah $8$.
• Pada hari ke-$4$, tingkat kepentingan jenis peristiwa $7$ adalah $7\times0=0$, jenis peristiwa $8$ adalah $8\times1=8$, dan jenis peristiwa $9$ adalah $9\times0=0$. Maka, nilai maksimumnya adalah $8$.
• Dari hari ke-$1$ hingga hari ke-$4$, tingkat kepentingan jenis peristiwa $7$ adalah $7\times1=7$, jenis peristiwa $8$ adalah $8\times2=16$, dan jenis peristiwa $9$ adalah $9\times1=9$. Maka, nilai maksimumnya adalah $16$.
• Dari hari ke-$2$ hingga hari ke-$4$, tingkat kepentingan jenis peristiwa $7$ adalah $7\times1=7$, jenis peristiwa $8$ adalah $8\times2=16$, dan jenis peristiwa $9$ adalah $9\times0=0$. Maka, nilai maksimumnya adalah $16$.

Masukan 2

8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

Keluaran 2

27
18
19
19

Penjelasan

Masukan ini memenuhi batasan Subsoal 3.

Masukan 3

12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

Keluaran 3

18
18
9
30
18
15
17
30
18
15
18
16
30
15
15