考点：队列

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：n ≤ 1e5
• 元素值域：a_i ≤ 1e9（注意整数类型选择，避免溢出）
• 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：队列

先进先出的结构，用于模拟排队过程或配合 BFS/单调队列。

思路框架（队列 通法 · 非本题专属）

1. 用双端队列 deque 实现，避免 list.pop(0) 的 O(n) 开销。
2. 单调队列可在滑动窗口中 O(n) 求最大/最小值。
3. 模拟类题目按时间顺序推进，注意同一时刻多个事件的先后。

实现要点：from collections import deque；popleft() 是 O(1)。

复杂度：时间 O(n) ｜ 空间 O(n)

该范式的通法易错点

• 用 list.pop(0) 造成 O(n²)。
• 忘处理队列为空的情况。

对照本题

• 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
• 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例

样例 1

• 输入：5 / 6 4 2 1 3
• 输出：12