Game, Game Everywhere

himuhasib Tough Cubs' Contest, Dece...
Limits 1s, 512 MB

Binary and Ternary are playing a game. In this game, they initially choose an array with N elements. Let the array elements be:

A[1], A[2], ... , A[N].

Then they play in turn. In each turn a player can choose two indices p and q such that the subarray from index p to index q is non-decreasing and pq. The same pair of indices cannot be chosen twice. Binary will choose a pair of index first, ternary will choose a pair next, and so on. The player who will be unable to choose a pair of indices in their turn will lose.

You have to determine who will win the game if two players play optimally.


There will be multiple test cases.

In the first line of input, there will be a number T (1 ≤ T ≤ 10) denoting the number of test cases. After that, every two lines will describe a test case.

In the first line of a test case, there will be a number N (2 ≤ N ≤ 105) denoting the array size. In the following line, the array of elements will be given. Each element will be separated by a single space. The array element will fit in a 32-bit signed integer.


For each test case, print a single line with the name of the winner.


1 2 1
1 2 2 1


Login to submit.


47% Solution Ratio
tasmeemrezaEarliest, Dec '16
mdvirusFastest, 0.1s
mdvirusLightest, 393 kB
mdvirusShortest, 346B
Toph uses cookies. By continuing you agree to our Cookie Policy.