Ruin The Friendship
"Should've kissed you anyway"
"Staying friends is safe
Doesn't mean you should"
On a rainy September afternoon, he was walking along Gallatin Street, lost in thought about the person he secretly liked. But he didn't know whether he should confess or not. He was afraid of losing a beautiful friendship. He kept walking, for \(N\) steps in a row. At step \(i\), he thought of message \(a_i\).
"My advice is always ruin the friendship."
"And my advice is always answer the question
Better that than to ask it
All you life
Should've kissed you anyway."
After \(N\) steps, Lakeside beach appeared before his eyes, and he decided he would confess everything he had been thinking about. However, he didn't know where to start. All he knew was that he wanted what he said to not repeat, and for the conversation to be as long as possible.
Please help him find the longest contiguous segment of steps he walked, such that the messages at those steps do not repeat.
Input
- The first line contains a positive integer \(N \ (1\le N \le 10^5)\);
- The next line contains \(N\) positive integers \(a_i \ (1\le a_i \le 10^5)\).
Output
- A single integer representing the length of that segment.
Scoring
- Subtask 1 (50%): \(N \le 10^3\).
- Subtask 2 (50%): No additional constraints.
Examples
Example 1
input 6 1 2 3 1 4 3
output
4
Explanation
The message segment [2, 3, 1, 4] does not repeat and is the longest such segment.
Comments