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

**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?

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.

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

5 4 2 1 4 3 1 2 5 5 3

5

- The students with secret number 1 are standing at positions 3 and 6. The distance between them is 6-3 = 3.
- The students with secret number 2 are standing at positions 2 and 7. The distance between them is 7-2 = 5.
- The students with secret number 3 are standing at positions 5 and 10. The distance between them is 10-5 = 5.
- The students with secret number 4 are standing at positions 1 and 4. The distance between them is 4-1 = 3.
- The students with secret number 5 are standing at positions 8 and 9. The distance between them is 9-8 = 1.

The maximum distance between any pair is 5.

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-2023

Page generated: 21 September 2023, 9:28pm AEST