Fermer Con 3SUM-u həll edir#9603
Fermer Con əmindir ki, alqoritmlərin işlənib hazırlanması sahəsində inqilabi bir kəşf edib: o, məşhur 3SUM məsələsi üçün, ümumiyyətlə qəbul edildiyi kimi ən azı kvadratik vaxt tələb edən, demək olar ki, xətti bir alqoritm hazırladığını iddia edir. 3SUM məsələsinin formalaşdırılmalarından biri belədir: tam ədədlərdən ibarət s_1, \ldots, s_m massivi verilmişdir. s_i + s_j + s_k = 0 şərti ödənilən müxtəlif i, j, k indekslərindən ibarət nizamsız üçlüklərin sayını tapmaq tələb olunur.
Fermer Conun alqoritmini yoxlamaq üçün Bessi tam ədəddən ibarət massivini hazırlamışdır. O, hər biri x_i, y_i (1 \le x_i \le y_i \le n) indeks cütünü təyin edən sorğu icra edəcək. Hər sorğu üçün Fermer Con A[x_i \ldots y_i] alt massivi üzərində 3SUM məsələsini həll etməlidir.
Fermer Con Bessinin yoxlamasından keçməsinə kömək etmənizi sizdən xahiş edir.
Birinci sətirdə n~(1 \le n \le 5000) və q~(1 \le q \le 10^5) tam ədədləri verilmişdir.
İkinci sətirdə massivin a_1, \ldots, a_n elementləri verilmişdir. Növbəti sətirdən hər birində bir sorğunu təyin edən x_i və y_i tam ədədləri verilmişdir.
Massivin hər bir a_i elementi üçün -10^6 \le a_i \le 10^6 şərtinin ödənildiyi zəmanət verilir.
sətir çap edin. -ci sətirdə -ci sorğunun cavabı olan bir tam ədəd olmalıdır.
Birinci sorğu üçün uyğun indeks üçlükləri (A_1, A_2, A_5) və (A_2, A_3, A_4)-dir.
Nümunə 1