AIOC Banner

Problem: Pairs

Want to try solving this problem? You can submit your code online if you log in or register.


Pairs

Input File: pairin.txt
Output File: pairout.txt
Time Limit: 1 second

It is the first day of December camp, and all 2N students have arrived safely. In a particularly lame icebreaking exercise, the tutors secretly divide all the students into pairs - they assign each student a secret number from 1 to N (using each number twice). The students then must try and find the other person with the same secret number (their partner).

At the start of the game, all the students organise themselves into a line. Some of them might be lucky and will be standing right next to their partner - we say that the distance between them is 1. In general, if two partners are standing at positions x and y in the line, we say that the distance between them is |x - y|.

What is the furthest distance between any two partners?

Input

The first line of input will consist of a single integer N, 1 <= N <= 100,000. The following 2N lines give the secret numbers of each of the students in the line.

Output

Your output file should consist of a single integer, the maximum distance between any pair of partners.

Sample Input

5
4
2
1
4
3
1
2
5
5
3

Sample Output

5

Explanation

The maximum distance between any pair is 5.

Scoring

The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2021

Contact: training@orac.amt.edu.au
Page generated: 22 September 2021, 11:45am AEST