"Simplex" P92739

You are working on a very difficult maximization problem. The function that you want to maximize is f(x) = c^Tx, subject to x ≥ 0 and Ax ≤ b, where x and c are n−dimensional vectors, A is an m × n matrix, and b is an m−dimensional vector.

You know that you could solve the problem using the simplex algorithm, but you convince yourself that you do not need it. So you decide to write a program that just assigns some random values to x, checks if the restrictions are fulfilled, and computes f(x), keeping track of the maximum value seen so far.

After weeks of computation, you realize that you are not finding very good results. This time you convince yourself that what you need is just more computational power. So, you adapt your program to run in different computers at the same time. You write a simple server that will run in your computer, and a client program P that you send to all our your friends, hoping that everyone will collaborate with you. The program P does very much the same as your first program: P gives random values to x, checks the restrictions, evaluates ‍f(x) and, each time that P finds a solution better than the best found so far at the same computer, P ‍sends ‍f(x) to the central server, which just appends it to a file, initially empty.

After several days, when you examine the file to take a look at the results found so far, you wonder how many of your friends have collaborated. As the file is rather long, you decide to write a program to help you to satisfy your curiosity.

Input

Input consists of several cases. Every case starts with the number 0 ≤ n ≤ 10⁵ of integer numbers stored in the file, followed by those numbers.

Output

For every case, print the minimum possible number of friends that have collaborated.