John is my good friend. He owns a company that provides internet to the wide public. He is trying to run his business well, but there are some malicious customers, that want to ruin him. His company gives every customer a direct connection to the internet through STP cables. Because he is very friendly and want to be best internet providers, he allows everyone to connect more than one computer so that everyone from the family can surf in the same time. But some users want to exploit this and get some cash by providing internet connection to their neighbours. So they buy cheap router and connect as many neighbours as possible to this network. But this is illegal. John now needs to detect this malicious customers and disconnect them. There is one way. Every machine with Windows installed produces very specific traffic. Every packet has its own ID. And Windows increases this ID value for every packet. So ID values of the traffic from one Windows machine may look like this: 1,2,5,8,12,265,348,556 etc.
When are two computers connected through router than the traffic will look like:
5,8,1,10,11,2,18,22,5 etc. (There is one sequence 5,8,10,11,18,22 and the other 1,2,5). John has log file from his central router which routes all traffic, so he has ID sequences from all IPs from his network. Now he needs to analyze them. Because he don't want to accuse nobody without real proof, he needs to calculate mininal count of Windows machines that can produce this traffic. (Because traffic 1,2,3 can be produced by one machine as well as three). Other OS doesn't do this, co we assume, that all machines have Windows installed (for who is clever enough to install other OSs, will never do such illegal things). Also you can assume that sequence from one machine will never overflow and thus start from the beginning again.
Task
You will be given sequence of integers and your task is to calculate minimal number of machines able to produce together such sequence.
Input
First line of input will contain one integer N less or equal to 1000000 followed by N lines. Every line contains one integer from the sequence between 0 and 1000000000.
Output
Write number of machines followed by new line.
Example
Input:
6
1
10
2
11
3
12
Output:
2
Explanation:
Only two or more computers can generate this sequence. Subsequences will be {1,2,3} and {10,11,12} or {1,10,11,12} and {2,3}.
Problem by Samuel BWPOW Kupka
|
|
Stredná