Xylophone là một nhạc cụ được chơi bằng cách gõ vào các thanh gỗ. Mỗi thanh luôn phát ra cùng một cao độ, nên đàn gồm nhiều thanh có cao độ khác nhau.

JOI mua một cây đàn gồm \(N\) thanh gỗ xếp thành một hàng, được đánh số từ \(1\) đến \(N\) từ trái sang phải. Thanh thứ \(i\) phát ra âm có cao độ \(A_i\), với \(1 \le A_i \le N\). Hai thanh khác nhau có cao độ khác nhau. JOI biết rằng thanh có cao độ thấp nhất nằm bên trái thanh có cao độ cao nhất.

JOI chưa biết cao độ của từng thanh và muốn xác định chúng. JOI có thính giác đặc biệt: khi nhiều âm thanh vang lên cùng lúc, cậu có thể nhận biết hiệu giữa cao độ cao nhất và thấp nhất. Với hai số nguyên \(s,t\) thỏa mãn \(1 \le s \le t \le N\), JOI có thể gõ đồng thời tất cả các thanh từ \(s\) đến \(t\), qua đó biết hiệu giữa giá trị lớn nhất và nhỏ nhất trong \(A_s,A_{s+1},\ldots,A_t\).

Hãy xác định cao độ của tất cả các thanh bằng không quá \(10000\) lần gõ như vậy.

Cài đặt

Với C++, khai báo #include "xylophone.h" và cài đặt hàm:

void solve(int N);

N là số thanh gỗ. Hàm solve được gọi đúng một lần cho mỗi bộ dữ liệu. Chương trình có thể gọi hai hàm do trình chấm cung cấp:

int query(int s, int t);
void answer(int i, int a);

query(s, t) trả về hiệu giữa cao độ lớn nhất và nhỏ nhất của các thanh có số hiệu từ \(s\) đến \(t\), kể cả hai đầu mút. Phải có \(1 \le s \le t \le N\). Không được gọi query quá \(10000\) lần. Vi phạm một trong các điều kiện này sẽ bị chấm Wrong Answer.

answer(i, a) thông báo rằng cao độ của thanh thứ \(i\) là \(a\), tức là \(A_i=a\). Phải có \(1 \le i \le N\). Không được gọi hàm này nhiều hơn một lần với cùng một giá trị \(i\), và phải gọi đúng \(N\) lần trước khi solve kết thúc. Vi phạm một trong các điều kiện này, hoặc thông báo sai cao độ của bất kỳ thanh nào, sẽ bị chấm Wrong Answer.

Trên LQDOJ, nộp đúng một tệp C++ cài đặt hàm theo chữ ký trên. Có thể cài đặt thêm các hàm phụ. Chương trình không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc tương tác với bất kỳ tệp nào khác; được phép ghi ra luồng lỗi chuẩn. Gói đính kèm chính thức vẫn được giữ để tham khảo, nhưng trình chấm của bài này chỉ hỗ trợ C++. Thông báo kỳ thi gốc quy định tối đa \(50\) lần nộp cho mỗi bài.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau; chương trình của bạn không được đọc trực tiếp dữ liệu này:

• Dòng đầu chứa \(N\).
• Dòng thứ \(1+i\) chứa \(A_i\), với \(1 \le i \le N\).

Dữ liệu ra

Nếu khi solve kết thúc, chương trình đã trả lời đúng cao độ của mọi thanh, trình chấm mẫu in Accepted : Q, trong đó \(Q\) là số lần gọi query. Nếu chương trình bị chấm sai, trình chấm mẫu in Wrong Answer.

Ràng buộc

• \(2 \le N \le 5000\).
• \(1 \le A_i \le N\) với mọi \(1 \le i \le N\).
• \(A_i \ne A_j\) với mọi \(1 \le i<j \le N\).
• Với hai chỉ số \(i,j\) thỏa mãn \(A_i=1\) và \(A_j=N\), luôn có \(i<j\).
• Không quá \(10000\) lần gọi query trong mỗi bộ dữ liệu.
• Giới hạn thời gian: \(2\) giây. Giới hạn bộ nhớ: \(256\) MB.

Phân nhóm

1. \(11\) điểm: \(2 \le N \le 100\)
2. \(36\) điểm: \(2 \le N \le 1000\)
3. \(53\) điểm: \(2 \le N \le 5000\)

Mọi nhóm đều thỏa mãn các điều kiện về cao độ và thứ tự vị trí của thanh thấp nhất, cao nhất nêu trên, cùng giới hạn \(10000\) lần gọi query.

Ví dụ giao tiếp

Với \(N=5\) và \((A_1,A_2,A_3,A_4,A_5)=(2,1,5,3,4)\), một trình tự tương tác là:

Nguồn

JOI Open 2018 - Xylophone, đề tiếng Anh, thông báo cài đặt và gói mã mẫu chính thức. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.