单调队列，望文生义，就是指队列中的元素是单调的。如：{a1,a2,a3,a4……an}满足a1<=a2<=a3……<=an,a序列便是单调递增序列。同理递减队列也是存在的。



1、如果队列的长度一定，先判断队首元素是否在规定范围内，如果超范围则增长队首。

2、每次加入元素时和队尾比较，如果当前元素小于队尾且队列非空，则减小尾指针，队尾元素依次出队，直到满足队列的调性为止

# 1. Non-negative Partial Sums(Southwestern European Regional Programming Contest 2011 - Gym 101561G - Uva 12393)

## Problem

### Description

You are given a sequence of n numbers a0, . . . , an−1. A cyclic shift by k positions (0 ≤ k ≤ n − 1) results
in the following sequence: ak, ak+1, . . . , an−1, a0, a1, . . . , ak−1. How many of the n cyclic shifts satisfy the
condition that the sum of the first i numbers is greater than or equal to zero for all i with 1 ≤ i ≤ n?

### Input

Each test case consists of two lines. The first contains the number n $(1 ≤ n ≤ 10^6)$, the number of
integers in the sequence. The second contains n integers a0, . . . , an−1 (−1000 ≤ ai ≤ 1000) representing the
sequence of numbers. The input will finish with a line containing 0.

### Output

For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the
condition stated above.

3
2 2 1
3
-1 1 1
1
-1
0

3
2
0

# 2. Miraculous Drug(Southeastern European Regional Programming Contest 2012, Gym 101472G)

## Problem

### Description

Input File: G.IN
Output File: standard output
Program Source File: G.C, G.CPP, G.JAVA

Joe is an enthusiast biomedical researcher. He is very close to discover the cure for a terrible
disease. In order to prepare the miraculous drug he needs to buy a special enzyme, that is quite
expensive and unfortunately loses its properties after a fixed period of time. Now Joe is in the
clinical trial phase. He needs a drug available at each hour. Thus he has to prepare exactly the
same quantity of drug every hour. The price of the enzyme might vary from hour to hour. The cost
of the enzyme on hour i is ci. The life time of the enzyme is h hours. Given the prices for the
next n hours, Joe has to find out the optimal cost to purchase enzymes such that the drug is
available in each of the n hours. If the price is the same Joe prefers to buy fresh enzymes, not to
stock them. We assume an unlimited quantity of enzymes is available each hour. Can you help
Joe?
The program input is from a text file. The file contains several data sets. A data set starts with the
number n (n<10000) of hours. Follows h (h<10000) the number of hours of the enzyme life
time, b the starting point, e the ending point of the printing interval (1≤b,e≤n), and the enzyme
costs ci (ci<10000), i=1..n. The program prints for each hour in the interval [b,e] the
number of enzymes Joe decides to buy.
White spaces can occur freely in the input. The input data are correct and terminate with an end
of file. For each set of data the program prints the result to the standard output from the beginning
of a line. An input/output sample is in the table below. There are two data sets. For the first one
n=6, h=3, b=1, e=6, and the costs are 5 4 4 3 5 6. The result consists of the numbers of
enzymes bought every hour, printed from the beginning of the line, separated with tabs.

6 3 1 6
5 4 4 3 5 6
3 3 2 3

1 1 1 3 0 0
1 1

❤采之欲遗谁，所思在远道。❤