Đây là một bài tập giao tiếp với máy chấm. Bài A và B chỉ khác nhau ở giới hạn n

Có một con mèo và $n$ chiếc hộp được đánh số từ $1$ đến $n$, ở ngày $0$ con mèo đang ở trong một hộp bất kỳ.

Mỗi đêm, nó sẽ bỏ ra chiếc hộp của mình và di chuyển sang chiếc hộp khác ở ngay cạnh chiếc hộp của nó, nói cách khác, nếu con mèo đang ở hộp thứ $i$, nó sẽ đi sang chiếc hộp thứ $i − 1$ (nếu $i − 1 ≥ 1$) hoặc chiếc hộp thứ $i + 1$ (nếu $i + 1 ≤ n$). Mỗi buổi sáng, bạn sẽ đi đến những chiếc hộp và được mở một chiếc hộp. Nếu bạn tìm thấy chú mèo, quá trình kết thúc. Nếu không, bạn đóng chiếc hộp lại và để lại chỗ cũ. Do sự kiên nhẫn của bạn có giới hạn, bạn chỉ có thể thực hiện quá trình này trong không quá $10^5$ ngày.