Go, Gophers!

Earlier this year, the Code Jam team planted an orchard with the help of an industrious gopher. It must have told other gophers, because we now have somewhere between 2 and 25 gophers living in the orchard. But it is hard to be sure exactly how many there are, because these gophers only emerge from their underground tunnels to eat at night, and we are too tired after a hard day of tree-pruning to stay up and watch for them. However, we do know how to make one "gopher snack" per day, which we can leave out each night to see whether it gets eaten. We think we can use this information to determine the number of gophers.

Here is what we know about the way that gophers eat. The N gophers meet during one day in a council to determine an order in which they will emerge over the following N nights, one at a time. Then, during each of the i-th of the next N nights, the i-th gopher in the order emerges and looks for a gopher snack. Each gopher has its own particular taste level (which never changes), and it will eat a snack if and only if the snack's quality level is at least as high as that gopher's taste level. During the day after the N-th gopher in the order has emerged, the gophers choose a new order and the process continues. Notice that even if a gopher chooses not to eat the snack that it finds, it still does not emerge again until it comes up in the next order chosen by the council.

We must make exactly one new gopher snack each day; even if a snack is not eaten, it spoils and cannot be reused the next night. Each morning, we learn whether or not the previous night's snack was taken.

Today, we know that the gophers are meeting in their council to determine their next order, so tonight will mark the start of that order. We are willing to devote some serious time to this investigation — as many as 105 nights. Using S or fewer snacks, can you help us figure out how many gophers there are?

문제

제한