Aterp took Ram and Shyam to a place where there was a never-ending queue of tiles. Aterp could see n tiles at a time. On the day before, he had written some number on the first n tiles from the left.
Ram was allowed to choose any tile with a number to initially stand on (say Xth). Shyam was asked to stand on the last tile with a number (the nth tile) with Aterp.
Ram and Shyam were given a task each:
Ram had to shout out the number written on the tile he is standing on.
Shyam had to write the number shouted by Ram on the adjacent tile on the right of him.
Both Ram and Shyam had to take one step to the right each time they performed their task.
Aterp jumped along with Shyam, and never left his side. Throughout the activity Aterp was looking leftwards keeping an eye on Ram. The game ends when all the tiles that Aterp could see at a time have the same number written on them.
Ram wanted to choose a starting position such that the game finishes as soon as possible. Can you help Ram choose this position X?
Input:
n = 4
Arr = { 1, 1, 2, 2}
Output: 3
Explanation: If Ram initially stands on the 3rd tile, in 2 moves tiles 5 and 6 will have the number 2 on it and Aterp would then see 4 2’s(tiles 3,4,5,6). Therefore the game would be over.