P16935 大图书管理员

:::info[题目背景] 石门之后的大殿，比三人先前见过的任何一处空间都更加安静。 那种安静并不是空无一物的死寂，而像某种被极其漫长的岁月层层压实之后，所留下的沉重沉默。高耸的石柱一直延伸到几乎看不清的穹顶，四周散落着破碎的灯座、倾斜的书架与剥落的石雕。金色的辉光依旧笼罩着整座殿堂，却不再显得温暖，反而像是某种凝固了太久的旧日余晖，安静地停留在这里，不肯彻底散去。 三人沿着大殿中央的长阶缓缓前行。 越靠近尽头，空气中的魔力就越发浓重。那并不是前面那些机关或魔物所散发出的、带着锋利压迫感的力量，而是一种更深、更古老，也更难以形容的东西。它没有立刻显露敌意，却让人本能地不想继续靠近，仿佛只要再向前一步，就会踏入某段早已不该被触碰的过去。 「这里……就是书库的核心了吗？」菲伦低声问。 「嗯。」芙莉莲轻轻点头，目光却始终落在高台最上方。 在那里，王座依旧静静耸立着。 它比从门外望见时更加高大，背后展开的石质纹样像一轮被层层封存起来的古老星图。只是，真正令人无法移开视线的，并不是王座本身，而是盘踞在它上方的那团东西。 那是一团难以用语言准确形容的魔法。 它没有固定的形状，像光，又像雾；像极缓慢流动的液体，又像一整片被强行压缩在一起的星辉。淡金与苍白交织的光在其中缓慢旋转，偶尔也会浮现出极细微的裂纹般的纹路，仿佛连时间本身都在它的表面发生了轻微的错位。仅仅只是注视着它，便会生出一种奇异的错觉——像是眼前这一瞬的呼吸，被悄悄拉长了；又像是某些已经过去很久的片段，正顺着记忆深处重新浮上来。 休塔尔克皱起眉，下意识压低了声音：「那到底是什么东西？」 芙莉莲安静地看了很久，才缓缓开口。 「是高浓度的古代魔法。」她说，「而且不是普通地残留在这里……它把这一带的时间也一起凝住了。」 菲伦微微一怔。 凝住时间——那已经不是寻常术式所能做到的事了。能将一整座书库的核心维持到千年之后，甚至直到此刻都还没有真正崩溃，这团魔法本身，恐怕已经接近某种危险的奇迹。可也正因如此，眼前这东西究竟该如何处理，反而没人能轻易给出答案。 继续放着不管，显然不行。 贸然破坏，也同样危险。 「总觉得……碰一下就会出大事。」休塔尔克低声说道。 「嗯。」芙莉莲的语气依旧平静，「大概真的会。」 可她并没有后退。 只是向前走上几步，站在王座之前，微微抬起头，注视着那团像是将千年时光都压缩其中的古老魔法。片刻之后，她像是终于确认了什么，缓缓抬起手，将自己的魔力一点点探了过去。 「芙莉莲大人？」菲伦下意识出声。 「我先试着和它产生共鸣。」芙莉莲轻声说道，「直接触碰太危险了，但如果能弄清楚它现在维持着怎样的术式结构，也许就能知道该怎么处理。」 那缕魔力极细，极轻，像一根几乎看不见的丝线，小心翼翼地没入那团凝滞的光之中。 下一刻，整座大殿忽然轻轻震动了一下。 并不剧烈，却像某种沉睡了千年的东西，在这一瞬间终于被唤醒。那团高浓度的古代魔法猛然亮起，淡金与苍白的光一层层向外扩散，像无声掀开的涟漪，顷刻间席卷了整座殿堂。菲伦几乎是本能地后退半步，休塔尔克也立刻握紧武器，可四周并没有发生爆炸，也没有出现冲击——真正开始变化的，是时间。 墙壁上的青苔，以肉眼可见的速度一点点褪去，地面上经年累月积下的尘埃缓缓消失，那些原本已经腐朽、发黑、边角卷曲的古老书籍，也在一排排书架上重新恢复了整洁与鲜明，封皮上的纹样变得清晰，书页重新变得洁白，连原本断裂倾倒的灯座与石雕，也像被一只无形的手耐心地扶正，回到了它们最初的位置。 整座「沉星书库」，竟像在这一瞬间被倒转了千年的风霜。 原本残破而沉寂的核心大殿，渐渐恢复成某种辉煌而完整的模样。晶灯一盏盏亮起，温和的光辉沿着穹顶与石柱流淌，书架高耸而整齐，古老的术式纹路在地面上安静延展，像一片终于再次苏醒的星图。空气中甚至浮现出隐约的人声与翻动纸页的细响，仿佛那些早已湮灭在岁月中的日常，并没有真正消失，只是被长久封存在了这团魔法之中，直到此刻才重新被投射出来。 菲伦怔怔地望着四周，连呼吸都不自觉放轻了几分。 「这不是幻觉……」她低声说道。 「嗯。」芙莉莲看着眼前不断展开的旧日景象，声音也轻了下来，「是它把曾经凝滞的时间，直接投射出来了。」 而在那片重新归来的辉煌之中，王座之上，也终于出现了真正的身影。 那并非某种怪物，也不是空荡荡的影子。 一道身着古老长袍的身影，正端坐在高处，安静地俯视着整座重新苏醒的书库。衣袍上的纹样庄重而繁复，手边放着尚未合起的厚重典籍，神情沉静得近乎没有波澜，像是早已习惯了守望这片无尽的藏书与时光。 坐在那座王座上的，正是千年前的大图书管理员。 在那个距今已逾千年的时代，人们对于魔法术式的拆解与复现还远没有如今这样成熟。许多强大的魔法一旦失传，便几乎再无人能够凭记忆将其还原，因此，魔法只能依靠魔导书被谨慎地记录、誊写与封存。也正因如此，守护一国藏书与术式传承的大图书管理员，其地位从来都不只是看守典籍的人而已——在某些以魔法立国的古老国度里，他们的分量，甚至完全等同于首席魔法师。 芙莉莲的目光很快落在那位大图书管理员手中的厚重典籍上。那本书的封面并不华丽，甚至因古老而显得格外沉静，可其上流转的微光，却与整座「沉星书库」中凝滞的时间彼此呼应。她几乎立刻便意识到，那正是这座书库里价值最高的典籍——「时间之书」。若真能掌握其中记载的术式，也许就不只是延缓、凝滞，甚至会拥有逆转时间、跨越空间的可能。 「说不定……就能再见上辛美尔一面了吧。」芙莉莲的心中，极轻地掠过了这样的念头。 下一刻，她微微俯下身，向王座上的大图书管理员致意。菲伦与休塔尔克见状，也立刻安静地随她一同低头行礼。高处那道沉静的身影并没有立刻开口，只是用仿佛早已洞悉一切的目光，平静地注视着他们。片刻之后，那位大图书管理员终于缓缓合上书页，声音低沉而悠远，像是穿过千年时光，仍旧清晰地落在这座书库之中。 「我早已预见，会有来自未来的访客抵达此处，并觊觎我手中的『时间之书』‌。」 「但想要取走它的人，必须先证明自己拥有与之相称的资格。」 他说到这里，目光依次掠过芙莉莲、菲伦与休塔尔克，古老而庄重的气息也随之在大殿中缓缓铺展开来。

图书管理员所管理的书库中拥有排成一排 $n$ 本典籍，编号为 $1\sim n$，编号为 $i$ 的典籍拥有重要度 $a_i$，因此典籍可以近似看作一个序列 $a$。 对于任意一个非空序列 $S$，我们定义与它**等长**的「索引序列」$T$ 为：$T_i$ 代表序列 $S$ 中满足 $S_j\geq i$ 的元素 $S_j$ 的个数，即 $T_i=\sum_{j=1}^{|S|}\mathbb{I}[S_j\geq i]$。我们定义序列 $S$ 的价值 $E(S)$ 为 $S$ 的下标与「索引序列」平方的乘积，即：$E(S)=\sum_{i=1}^{|S|} i\times T_i^2$。 图书管理员向芙莉莲一行人抛出了 $q$ 个问题，每个问题包含两个正整数 $l$ 和 $r$，表示拿出编号为 $[l, r]$ 内的连续典籍构成典籍序列 $S$ 后，这些典籍的价值 $E(S)$ 有多大？ 针对每个问题，输出 $E(S)$ 对 $10^9+7$ 取模的结果。

第一行包含两个整数 $n, q(1\leq n, q\leq 10^5)$，分别表示典籍的数量和图书管理员询问的次数； 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n(1\leq a_i\leq 10^9)$，表示编号为 $i$ 的典籍的重要度； 接下来的 $q$ 行，每行包含两个整数 $l, r(1\leq l\leq r\leq n)$，表示一次问题的左端点和右端点。

共 $q$ 行，每行输出一个整数，表示对应查询的 $E(S)$ 对 $10^9+7$ 取模的结果。

对于第一个问题，$S=[3, 1, 4, 1, 5]$，「索引序列」$T=[5, 3, 3, 2, 1]$，价值为 $1\times 5^2+2\times 3^2+3\times 3^2+4\times 2^2+5\times 1^2=91$；对于第二个问题，$S=[1, 4, 1]$，「索引序列」$T=[3, 1, 1]$，价值为 $1\times 3^2+2\times 1^2+3\times 1^2=14$；对于第三个问题，$S=[4]$，「索引序列」$T=[1]$，价值为 $1\times 1^2=1$。 $\mathbb{I}[·]$ 为示性函数，若括号内的表达式为真，则函数值为 $1$，否则函数值为 $0$。 :::info[题目背景] --- 大图书管理员沉默地注视了他们许久。 那目光并不锋利，也没有刻意的威压，只像是在漫长岁月之后，终于等到了一个足以托付答案的人。片刻之后，他缓缓点了点头，原本始终平静无波的神情里，终于多出了一丝近乎欣慰的意味。高处的王座依旧笼罩在柔和而庄严的光辉之中，而他只是将那本厚重古老的「时间之书」轻轻合上，随后抬起手，将它递向了阶下的芙莉莲。 「你们的表现，足够令人满意。善用它，你们一定会做出正确的选择。」 芙莉莲安静地走上前去，伸出双手，郑重地接过了那本承载着千年时光的典籍。 而就在她指尖触碰到封面的瞬间，整座大殿忽然轻轻震颤了一下。 那并不是战斗时那种剧烈的轰鸣，更像某个被强行延续至今的梦境，终于走到了尽头。四周温暖而辉煌的光一点点暗淡下去，空气里隐约浮动的人声与翻书声也渐渐远去。书架上那些方才还崭新整洁的典籍，以肉眼可见的速度重新腐朽、发黑，书页卷曲，边角碎裂；高耸的石柱表面重新浮现出斑驳裂痕，金属灯座与王座的边缘也缓缓爬上了暗红色的锈迹。地面失去了先前那种光洁与完整，裂纹之中重新渗出潮湿，细密的青苔一点点覆上石缝，仿佛千年的风霜正沿着时光的断面，重新落回这座「沉星书库」之上。 王座上的那道身影，也在这片缓慢崩塌的旧日光景中一点点变淡，最终只剩下一片安静而模糊的轮廓。 菲伦怔怔地望着四周，轻轻屏住了呼吸。休塔尔克也下意识握紧了手中的武器，直到确认一切都只是恢复原状之后，才慢慢放松下来。唯有芙莉莲低头看了一眼怀中的「时间之书」，随后抬起头，望向重新变得残破而沉寂的大殿，语气依旧平静得像是在陈述一件再自然不过的事实。 「看来我们回来了呢。」