theGameAfter30thSeaGames

Mới hôm nọ vừa phán một câu cực mạnh là sẽ chỉ gặp đội tuyển Thái Lan chứ không gặp U22 Việt Nam, quả nhiên huấn luyên viên Kim cũng gặp được người đồng nghiệp Nishino cùng đội của ông, nhưng không phải trên sân bóng mà là ngay tại sân bay để trở về quê nhà. Vì sợ hai người bạn của mình đứng một mình tủi thân, huấn luyện viên Dalmas quyết định tặng Việt Nam 4 bàn rồi sửa soạn hành lý ra ngồi cùng hai ông bạn cho vui. Thấy anh em đã đông đủ, cả ba người rủ nhau chơi một trò chơi vô não: trò chơi sẽ bắt đầu với hai người và n rổ bóng, mỗi rổ bóng có k quả bóng. Đến lượt của ai, người đó sẽ bốc nhiều nhất một quả từ nhiều rổ khác nhau, tối thiểu phải bốc 1 rổ. Ai bốc được quả cuối cùng sẽ là người chiến thắng. Đang trong tâm trạng tức tối, cả ba người quyết không nhường nhịn nhau và sẽ chơi tới cùng.

Cho một tập basketOfBalls gồm các số nguyên, phần tử thứ i có giá trị là số bóng trong rổ thứ i. Vì hai người chơi sẽ chơi tối ưu, hãy trả về 1 nếu người đi trước sẽ thắng, ngược lại trả về 2 nếu người đi sau thắng. Hãy giúp ba người có một cuộc chơi gay cấn trước khi phải bay về nước nhé!

Ví dụ:

• Với basketOfBalls = {1,2} thì theWinnerOfLosers = 1;
  Người đi trước có thể chọn 1 quả từ rổ thứ nhất, người đi thứ hai chỉ được lấy 1 quả từ rổ thứ 2. Lấy quả cuối cùng ở rổ thứ 2 và người đi trước sẽ giành chiến thắng.
• Với basketOfBalls = {2,2} thì theWinnerOfLosers = 2;
  Nếu người đi trước chọn 1 quả từ 1 rổ bất kì, người thứ 2 chỉ cần lặp lại quả trình từ ví dụ 1 và giành chiến thắng.
  Nếu người đi trước chọn 2 quả từ 2 rổ, người thứ 2 chỉ cần chọn 2 quả còn lại từ 2 rổ và giành chiến thắng.

Đầu vào/Đầu ra:

• [Thời gian] 0.1s với C++, 0.6s với Java và C#, 0.8s với Python, Go và JavaScript.
• [Đầu vào] Integer.Array basketOfBalls
  Số bóng ở mỗi rổ.
  1 ≤ basketOfBalls.size() ≤ 10^9
1 ≤ basketOfBalls[i] ≤ 10^9
• [Đầu ra] Integer
  Trả về số 1 nếu người đi trước thắng, 2 nếu người đi sau thắng.