Alimcan ACM-i sevir
Aлимcan növbəti kombinator məsələsini həll etməyə çalışır. O, proqramçıların massivlər və ikilik ədədlərlə maraqlandığını bilir. Buna görə də, m (0 ≤ m ≤ 2^n - 1) ədədi və a[0], a[1], ..., a[n-1] massivinə əsaslanaraq f[a](m) funksiyasını yaratdı.
burada b[0], b[1], ..., b[k-1] m ədədinin ikilik təqdimatında vahidlərin indeksləridir.
Məsələn, f[a](5) = a[0] + a[2] və f[a](11) = a[0] + a[1] + a[3].
Birdən Aлимcanın daxili səsi qışqırdı: "Elə m-lərin sayını hesablayın ki, f[a](m+1) > f[a](m) olsun!!!". Bu problemi ACM-ə daha çox bənzətmək üçün Aлимcan sizdən q sorğularına cavab verməyinizi xahiş edir.
Sizə q cüt ədədləri l[i], r[i] (0 ≤ l[i] ≤ r[i] ≤ n - 1) verilir. Hər bir sorğu üçün i c[i] = (a[li], a[li+1], ..., a[ri]) massivini nəzərdən keçirin. Elə m-lərin sayını hesablayın ki, (0 ≤ m ≤ 2^(r-l+1) - 1), f[c](m + 1) > f[c](m) olsun.
Giriş məlumatları
Birinci sətir n tam ədədini (1 ≤ n ≤ 2 * 10^5) - a massivinin uzunluğunu ehtiva edir.
İkinci sətir n tam ədədləri a[0], a[1], ..., a[n-1] (-10^9 ≤ a[i] ≤ 10^9) - a massivinin elementlərini ehtiva edir.
Üçüncü sətir q ədədini - sorğuların sayını ehtiva edir.
Növbəti q sətirin hər biri l[i], r[i] (0 ≤ l[i] ≤ r[i] ≤ n - 1) cüt tam ədədlərini ehtiva edir.
Çıxış məlumatları
Hər bir sorğu üçün bir tam ədəd çıxarın - ona cavab. Cavabı 10^9 + 7 moduluna görə çıxarın.