# Google interview quesrtion: Ross and Monica guess game

(0)

Ross and Monica are playing a guessing game.

Ross has a number T = X + 0.5 where X is an integer btw 0 and N (inclusive). Monica attempts to guess this number by asking one question: “Is i greater than or lesser than your number?” for some integer i btw 1 and N (inclusive). Ross responds to Monica’s question by drawing a > (greater than) or < (lesser than) sign on the quiz board.

Monica being the competitive person that she is, comes up with a strategy to guess Ross’ number. Before making any guesses, she creates a list of N numbers, where every number from 1 to N occurs exactly once in any order. Then she goes through the list one by one, in the exact same order. But she skips any unnecessary guesses. That is, if the number she’s about to guess is i and she had previously guessed some j < i and Ross told her it was greater than T, then she would skip over i. Using this strategy, Monica is always able to accurately determine i, regardless of the list she creates.

Ross hasn’t determined the value of T but he knows the list of numbers Monica is about to use.

Help Ross find the number of times he’ll draw a < (lesser than) sign immediately after drawing a > (greater than) sign on the quiz board for each possible value of X where T = X + 0.5.

Input
6
5 1 2 4 3 6

Output
0
1
1
2
1
0
0