Bạn đang tham gia trò chơi "đoán số hay, rinh lộc ngay" với cơ hội nhận về giải thưởng vô cùng hấp dẫn. Để trở thành người thắng cuộc, bạn cần vượt qua tất cả ~P~ vòng chơi. Ở mỗi vòng chơi, chương trình có một con số bí mật ~V~ và bạn cần tìm ra ẩn số này. Trước khi trò chơi bắt đầu, ban tổ chức thông báo một số nguyên ~D~ và cho bạn gợi ý: Ẩn số cần tìm ~V~ trong tất cả ~P~ vòng chơi đều là một số nguyên không nhỏ hơn ~1~ và không lớn hơn ~D~. Mỗi vòng chơi gồm một số lượt đoán số. Mỗi lượt đoán số diễn ra như sau: Bạn dự đoán một số nguyên ~H \in [1, 10^9]~. Ngay sau đó, ban tổ chức sẽ cho bạn biết các thông tin sau:

• Số ~H~ bạn đưa ra có trùng khớp với ẩn số ~V~ của chương trình hay không.
• Nếu không trùng khớp, bạn sẽ nhận được thông báo một giá trị ~X~ được xác định theo quy tắc sau:
  • Đặt ~X = \max(0, 1 - \frac{|V - H|}{V})~
  • Làm tròn giá trị ~X~ tới chính xác ba chữ số ở phần thập phân.

Bạn được coi là chiến thắng một vòng chơi nếu tìm ra ẩn số của chương trình sau không quá ~69~ lượt đoán số. Vượt qua cả ~P~ vòng chơi, bạn sẽ nhận được giải thưởng từ chương trình. Số lượt dự đoán số càng ít, giải thưởng của bạn càng lớn.

Tương tác

Đầu tiên, chương trình của bạn đọc hai số nguyên ~P~ và ~D~ (~1 \le P \le 1000; 1 \le D \le 10^9~) lần lượt là số vòng chơi và giới hạn ~D~ được thông báo trước khi trò chơi bắt đầu.

Tiếp theo, mỗi lượt đoán số diễn ra như sau:

• Trước tiên, bạn in ra số nguyên ~H~ (~1 \le H \le 10^9~) là con số bạn dự đoán.
• Sau đó, bạn đọc vào một số nguyên ~R~ (~R \in \{-1, 0, 1\}~) thể hiện phản hồi từ chương trình, cụ thể như sau:
  • ~R = 1~: giá trị ~H~ trùng khớp với ẩn số ~V~ cần tìm và bạn đã chiến thắng vòng chơi. Khi đó, chương trình của bạn cần chuyển sang vòng chơi tiếp theo, hoặc kết thúc ngay nếu đây là vòng chơi cuối cùng.
  • ~R = -1~: giá trị ~H~ bạn đưa ra không hợp lệ, hoặc bạn đã đoán vượt quá số lần cho phép. Khi đó, chương trình của bạn cần kết thúc ngay.
  • ~R = 0~: giá trị ~H~ chưa trùng khớp với ẩn số cần tìm. Khi đó, bạn đọc vào một số thực ~X~ được tính theo quy tắc ở trên.

Lưu ý: Sau khi bạn in ra một số nguyên, bạn cần in ra ký tự xuống dòng và thực hiện thao tác flush luồng ra chuẩn bằng cách gọi các lệnh sau:

• fflush(stdout) hoặc cout.flush() trong C++;
• System.out.flush() trong Java;
• stdout.flush() trong Python;

Chấm điểm

Nếu bạn không chiến thắng toàn bộ ~P~ vòng chơi, bạn được ~0~ điểm. Ngược lại, gọi ~Q~ là số lượt đoán số nhiều nhất bạn cần sử dụng trong một vòng chơi, số điểm của bạn được tính như sau:

• Nếu ~Q \le 25~, bạn được ~100\%~ số điểm của test.
• Nếu ~25 < Q \le 36~, bạn được ~((36 - Q)^2 \cdot 0.3 + (36 - Q) \cdot 1.7 + 45)\%~ số điểm của test.
• Nếu ~36 < Q \le 69~, bạn được ~((96 - Q)^2 \cdot 0.01 + 9)\%~ số điểm của test.

Scoring

• Subtask ~1~ (~4\%~ số điểm): ~D = 20~.
• Subtask ~2~ (~8\%~ số điểm): ~D = 100~.
• Subtask ~3~ (~8\%~ số điểm): ~D = 1000~.
• Subtask ~4~ (~16\%~ số điểm): ~D = 10^6~.
• Subtask ~5~ (~28\%~ số điểm): ~D = 5 \cdot 10^8~.
• Subtask ~6~ (~36\%~ số điểm): ~D = 10^9~.

Example

Giang gọi một dãy số là một khối nếu dãy số đó có độ dài là ~k+1~, và phần tử đầu tiên của dãy là ~k~ (~k~ có thể là số nguyên dương bất kỳ).

Ví dụ, ~(2,1,2)~ hoặc ~(1,2)~ là một khối, tuy nhiên ~(2,1)~ không phải một khối.

Giang gọi một dãy số là đẹp nếu có thể tồn tại một cách lặp lại các thao tác dưới đây cho đến khi dãy trở thành dãy rỗng (không còn phần tử nào):

• Chọn một đoạn con liên tiếp trong dãy sao cho đoạn con được chọn là một khối.
• Xóa đoạn con được chọn khỏi dãy và dồn các phần tử phía sau lên trước.

Ví dụ, ~(1,2,1,2,1,4,4)~ là một dãy đẹp vì có thể xóa dãy như sau:

• Chọn đoạn ~(1,2)~ bắt đầu ở vị trí ~3~. Hiển nhiên đoạn này là một khối. Xóa đoạn khỏi dãy. Dãy trở thành ~(1,2,1,4,4)~.
• Chọn đoạn ~(2,1,4)~ bắt đầu ở vị trí ~2~. Hiển nhiên đoạn này là một khối. Xóa đoạn khỏi dãy. Dãy trở thành ~(1,4)~.
• Chọn đoạn ~(1,4)~ bắt đầu ở vị trí ~1~. Hiển nhiên đoạn này là một khối. Xóa đoạn này và dãy trở thành dãy rỗng.

Giang đưa cho Huy một dãy ~a_1, a_2, …, a_n~. Cô đố Huy đếm xem có bao nhiêu đoạn con liên tiếp của dãy ~a~ là dãy đẹp. Tuy nhiên Huy còn bận làm một số việc khác nên không chưa thể trả lời câu hỏi này. Bạn hãy trả lời giúp Huy nhé.

Đoạn con liên tiếp là một đoạn con thu được bằng cách xóa không, một hoặc một vài phần tử ở đầu và cuối dãy và giữ nguyên thứ tự các phần tử còn lại. Ví dụ, ~(3, 4), (3, 4, 5)~ hay ~(1)~ đều là các đoạn con liên tiếp của ~(1, 2, 3, 4, 5)~ nhưng ~(1, 3)~ hay ~(3, 2)~ thì không. Đoạn con liên tiếp gồm các phần tử ở vị trí thứ ~l~ đến vị trí thứ ~r~ có thể được gọi là đoạn ~(l, r)~.

Dữ liệu - Nhập từ tệp văn bản DRANGE.inp:

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 7000)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le n)~.

Kết quả - Ghi ra tệp văn bản DRANGE.out:

• Một dòng duy nhất gồm số lượng đoạn con liên tiếp của dãy ~a~ là dãy đẹp.

Chấm điểm

Ví dụ

Dữ liệu (DRANGE.inp)

5
1 2 1 2 4

Kết quả (DRANGE.out)

5

Giải thích

• Các đoạn ~(l, r)~ là đoạn đẹp trong dãy là: ~(1,2),(2,4),(3,4),(1,4),(1,5)~.