
ZOJ Problem Set  3297
As all you know, MM loves cookies very much and now she's going to make another cookie choice! There is a sequence of N cookies while there may be K different kinds of cookies. MM wants to choose a continuous subsequence of cookies to eat (the subsequence may be empty), while for each kind of cookie, there are minimum and maximum numbers MM want to choose. But DD wants to minimize the length of chosen continuous subsequence (for his poor wallet). You are to find the shortest continuous sequences that satisfy MM's requirement. Formally speaking, define the cookie sequence as C_{i} (1<=i<=N, 1<=C_{i}<=K), where C_{i} is the kind of the ithe cookie, and the chosen continuous subsequence has M_{i} cookies of kind i. M_{i} must satisfy A_{i}<=M_{i}<=B_{i}. While A_{i} and B_{i} are given miminum and maximum numbers of kind i to choose. InputAbout 20 test cases, seperated by blank line. First line of each case is two integers N (1<=N<=400000) and K (1<=K<2048). The second line is N numbers of sequence C. The following K lines, the ith line has two numbers A_{i} and B_{i}. All numbers are integers. OutputFor each test case, output the minimum length of chosen continuous subsequence. If no answer, output 1. Sample Input5 2 1 2 2 2 1 2 4 1 3 7 2 1 2 1 2 1 2 1 3 4 0 1Sample Output 5 1 Author: CUI, Tianyi Source: ZOJ Monthly, February 2010 