A line of n buoys is anchored at regular intervals along a straight shipping channel, numbered 0 through n-1 from one end of the channel to the other. Each buoy continuously flashes a signal light in one particular color, identified by an integer id. To warn passing ships of a hazard between two mismatched markers, the harbor authority wants to find two buoys, at positions i and j, that flash different colors and are as far apart along the channel as possible. Determine the maximum possible value of |i - j| over all pairs of buoys whose colors differ. It is guaranteed that not every buoy flashes the same color, so at least one such pair exists.
The first line contains a single integer n, the number of buoys. The second line contains n space-separated integers c_0, c_1, ..., c_{n-1}, where c_i is the color id flashed by the buoy at position i.
Print a single integer: the maximum value of |i - j| over all pairs of positions i, j (0 <= i, j <= n-1) such that c_i != c_j.
Example 1
Input
7 1 1 1 6 1 1 1
Expected
3
Explanation
Buoy 3 flashes color 6 while every other buoy flashes color 1. The farthest mismatched pair is (0,3) or (3,6), both giving |i-j| = 3, which is the maximum.
Example 2
Input
6 3 3 3 3 3 7
Expected
5
Explanation
Only buoy 5 flashes color 7; every other buoy flashes color 3. Pairing buoy 0 (color 3) with buoy 5 (color 7) gives |0-5| = 5, the largest possible distance in a line of 6 buoys.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →