Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1495
Stacking Tower

Time Limit: 2 Seconds      Memory Limit: 65536 KB

One of the most common children's toys is a stacking tower, which consists of a series of rings of di erent sizes and a tapered rod which can hold the rings. The rings and rod are designed so that when the rings are placed in descending order by size, they fit exactly on the rod. Further, each ring, if placed by itself on the rod will go no lower than its position when all rings are on the rod. The diagram on the left shows an example of this toy which uses five rings, numbered 1 (smallest) to 5 (largest)

Unless endowed with super-genius mental faculties, most infants will place the rings in a random order on the rod, which results in some rings sticking over the top of the rod. The above diagram on the right shows the result of one such random placement. Your job will be to determine the number of rings which sit above the rod given a random ordering of the rings. You may assume that the rings may be stacked arbitrarily high without falling over.


Input will consist of multiple problem instances. Each instance consists of a single line of the form n r1 r2 ... rn. The positive integer n specifies the number of rings (<= 100), and the remaining n integers give the order the rings are put on the rod. A value of n = 0 will terminate input.


For each problem instance, you should output one line containing an integer indicating the number of rings sticking over the top of the rod.

Sample Input

5 5 4 3 2 1
5 4 5 1 3 2
8 1 2 3 4 5 6 7 8
20 11 10 19 7 12 14 5 2 3 1 8 6 13 17 18 9 4 20 15 16

Sample Output


Source: East Central North America 2002
Submit    Status