← 返回题目列表

Codeforces · 2141/C

C. 子数组的最小值

中文机器翻译题面 查看原题

有一个变量$$$sum$$$,它最初等于$$$0$$$。

还有一个数据结构可以执行以下操作:

  • 抵制 x — 将值为 $$$x$$$ 的元素添加到结构的末尾;
  • 推前 x — 将值为 $$$x$$$ 的元素添加到结构的开头;
  • 弹出 — 从结构中删除最后一个元素;
  • 弹出窗口 — 从结构中删除第一个元素;
  • 分钟 — 将结构中当前最小元素的值添加到变量 $$$sum$$$ 中。

操作 弹出, 弹出窗口,和 分钟 不能应用于空结构!

使用此结构,您希望能够找到 $$$a$$$ 元素的数组 $$$a$$$ 的所有非空子数组的最小值之和。

更正式地说,您的任务是找到不超过 $$$n \cdot (n + 2)$$$ 命令的序列,使得在所有操作之后,对于任何可能的数组 $$$a$$$,变量 $$$sum$$$ 将等于 $$$\sum_{0 \le l \le r \lt n} \min(a[l],\dots, a[r])$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 数组中的元素数量。

输出

输出 $$$k$$$ ($$$1 \le k \le n \cdot (n + 2)$$$) 命令。每个命令必须是以下五行之一:

  • "抵制 a[i]",其中 $$$i$$$ — 从 $$$0$$$ 到 $$$n - 1$$$ 的数字
  • "推前 a[i]",其中 $$$i$$$ — 从 $$$0$$$ 到 $$$n - 1$$$ 的数字
  • "弹出"
  • "弹出窗口"
  • "分钟"

如果有多个有效答案,则输出任意一个。

示例

输入
复制

1

输出
复制

3
pushback a[0]
min
popfront

输入
复制

2

输出
复制

6
pushfront a[1]
min
pushback a[0]
min
popfront
min