2015-16 Woburn Challenge Finals - Senior Division
The Center for Exploration of Monkey Cryptography (CEMC) is an organization dedicated to wartime cryptography research amongst the primate community. As the monkeys are once again at war with the cows, this institution has become indispensable to their success in combat. After all, taking over Scarberia in the 21st century will require some of the most sophisticated code-breaking techniques in existence to infiltrate the enemies' communications. As it turns out, the cows possess a slight technological edge over the monkeys, due to their experimentation with Cow-Bots in 2002. They were therefore able to reverse engineer the structure of the CEMC's servers!
The cows have learned that the server is a network consisting of computers arranged in a line topology. Specifically, the computers are numbered from to , and are connected in a line in ascending order. For example, computer is connected only to computer , computer is connected only to computers and , and computer is connected only to computer . The network is encrypted using a simple public key cryptosystem. Each computer has a distinct public key, an integer . The private key to access computer is a sequence of integers based on the prime factorization of . Consider with the prime factorization of when the prime factors are listed in ascending order. Its private key is then the sequence .
Typical brute force attacks rely on trying every possibility to gain access. In this case, a private key is easier to guess if it comes "earlier" in an exhaustive list of possible guesses. So for two different computers and , we will call the public key of weaker than the public key of if and only if the private key sequence of is lexicographically smaller than the private key sequence of . A sequence is considered to be lexicographically smaller than another sequence if for the smallest index such that differs from . If every value in is equal to the values at corresponding indices in and is a shorter sequence (i.e. if is a prefix of ), then is also considered lexicographically smaller than . For example, is lexicographically smaller than and is lexicographically smaller than .
Having discovered the weak cryptographic scheme of the CEMC's servers, the cows now wish to assert their dominance and generate chaos amongst the monkeys by performing a distributed denial-of-service (DDOS) attack on the network to take it down. However, they will need a weakpoint from which to initiate the attack. In particular, a weakpoint is a computer whose public key is weaker than that of every other computer that it is directly connected to. Please help the cows write a program to find a weakpoint and crash the CEMC's servers. If there are multiple such weakpoints, then any one of them will suffice.
In test cases worth of the points: .
Input Specification
The first line of input consists of a single integer .
lines follow, with the -th of these lines containing (for
).
Output Specification
Output a single integer between and , your chosen weakpoint.
Sample Input
4
840350
341796875
1584
735166567
Sample Output
1
Explanation
Computer 's public key has the prime factorization
, so its private key is .
Computer 's public key has the prime factorization
, so its private key is .
Computer 's public key has the prime factorization
, so its private key is .
Computer 's public key has the prime factorization
, so its private key is .
Therefore, both computers and are valid weakpoints that will be accepted.
Comments