题目地址:https://www.luogu.com.cn/problem/P2629

题意：有n个消息，每个消息有一个权值，这n个消息本身就有一个自己的排序（按照输入给出的顺序）1....n，现在你需要读取这n个消息，你一共有n种读取的顺序。k k+1 k+2....n 1 2 .. k-1.现在需要满足的是，你的这种方法的任意前i个数之和不小于0.问满足这样的读取顺序有多少种。

输入：第一行n。第二行n个整数，分别表示每个消息的权值

输出：满足条件的方案数目

题解：首先观察有n种读取方式，那么便可以将这n个消息看成是一个环形排列，从中任意一个点切开就是一种读取方式。而在数据结构中，可以使用双倍空间表示这种存储方式，即1 2 3...n 1 2 3 .. n那么只需要从中选取连续的n个数就是一种读取方式。那么现在需要解决的问题就是选择的这种读取方式是否满足条件。例如选取的是第i个数到第i+n-1个数，那么只需要这n个数中的前缀的最小值pre[j]大于等于pre[i-1]即可。对于这种方式的区间最小值，便可以使用单调队列来实现，也就是使用双端队列就可以了。

AC代码：