七千四百号的回响
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

在猎户座悬臂的暗缘,一颗红巨星步入演末阶段. 人类历时三百七十九载,将其十二颗行星拆解重构,编织成环绕恒星的银灰色巨构——弗里曼·戴森架构第一阶段,「烛龙」能源矩阵已持续运行七个世纪.
这不是经典意义上的固态球壳,而是由四千八百万个六边形模块组成的动态环带. 每个模块面积相当于古地球的亚欧大陆,表面覆盖着可自我修复的非晶态硅-碳纳米复合材料,光电转换效率逼近理论极限. 模块间以引力锚链耦合,构成环绕恒星的超级结构,每秒钟汲取的能量足以重启一颗类木行星的核聚变.
建造者的后裔栖息于环内生态区,透过可抵御日冕抛射的量子隧穿玻璃,凝视这颗被束缚的恒星. 它如同熔炉中的囚徒,巨大的能量束如银白色血管从日冕中延伸,注入环带深处. 这里没有自然昼夜,只有能量潮汐的周期性脉动,标记着文明的时间尺度.
在环带控制中枢,你——「烛龙」的首席工程师注视着深空监测阵列的异常读数. 连续七个标准周期,第七千四百号引力平衡器持续输出规律性微引力涟漪. 其模式不属于任何已知协议或故障,精度超越人类工程学极限——仿佛以恒星引力波为琴键,演奏无声的乐章.
异常源表现出更令人警觉的特性:它对「烛龙」的能量调度产生协同响应. 每当矩阵调整输出,引力涟漪的频率便在0.7秒延迟后发生精确匹配变化. 这种超距互动暗示着智能介入.
侦察舰队穿越环带外侧的尘埃屏障,抵达异常坐标. 虚空之中空无一物,但探测器捕捉到时空曲率的细微扭曲——一个完美到令人战栗的几何结构印记. 它并非自然形成,而是某种存在停留观测后,以超光速方式离去时在引力场中留下的「足迹」.
没有信息,没有接触. 但当工程师调取环带建造初期的引力波背景数据时,发现了令人冰寒的真相:同样的几何印记,其实早在一千年前就已出现在猎户座悬臂的监测记录中——其出现时间,精确对应人类议会投票启动「烛龙」计划的那一秒.
更深远的数据挖掘揭示,这种印记在银河系历史中曾出现十七次,每次都标记着一个文明达到卡尔达舍夫II型巅峰的时刻. 而在所有案例中,该印记出现后,那些文明均在三个世纪内归于沉寂.
控制室外的星空依旧沉默,但你明白,人类并非建造者,而是被观察者.「烛龙」环带不是文明的巅峰,而是某个宇宙尺度实验的终点标记. 那个持续跳动的引力信号,不是问候,不是威胁,而是倒计时开始的钟声.
很远处似乎传来了一声清脆的声音——谁把高脚杯打碎了?
作为首席工程师,你常年都在研究第七千四百号引力平衡器所输出的微引力涟漪,在过去一个标准周期内,平衡器一共输出了 n 次微引力波动,每次波动的幅值是 a_i.

然而,当这些数据保存在重力井存储单元的时候,日冕突然抛射出了巨量的中微子,存储单元内的数据发生了严重损害,具体地,恒星一共进行了 m 次中微子抛射,每一次都修改了下标为 [l_i, r_i] 的数据,使其变成了自身的相反数.

你——「烛龙」的首席工程师,对于恢复这种损坏程度的数据而言当然不在话下,于是你迅速抄起键盘,工作了起来……

输入描述:

第一行包含一个正整数 n (1\leq n\leq 5 \times 10^5),代表第七千四百号引力平衡器在过去一个标准周期内输出的微引力波动数量.

第二行包含 n 个整数 a_i (-10^9\leq a_i\leq 10^9),代表每次波动的幅值.

第三行包含一个非负整数 m (1\leq m\leq 5 \times 10^5),代表中微子抛射的次数.

以下 m 行,每行两个正整数 l_i, r_i (l_i\leq r_i),代表本次中微子抛射修改了下标为 [l_i, r_i] 的数据,使其变成了自身的相反数.

输出描述:

输出一行包含一个整数 S =\sum a_i,代表数据恢复后的微引力波动幅值的和.
示例1

输入

复制
5
1 2 -1 5 3
2
1 3
3 5

输出

复制
-12

说明

对于第一组样例,第二次抛射修改了 [3, 5] 的值,因此第二次抛射前数据为 \{1, 2, 1, -5, -3\};第一次抛射修改了 [1, 3] 的值,因此第一次抛射前数据为 \{-1, -2, -1, -5, -3\},求和后为-12.
示例2

输入

复制
6
1 1 4 5 1 4
5
1 6
1 6
2 2
3 3
4 4

输出

复制
-4

说明

对于第二组样例,不难恢复出发生抛射前的数据是 \{1, -1, -4, -5, 1, 4\},求和后为-4.