2026 · HSG THCS · Quảng Trị

Số chính phương là bình phương của các số tự nhiên. Ví dụ: 4, 9, 16 là các số chính phương; 3, 8, 10 không phải là số chính phương.

Yêu cầu: Cho đoạn số nguyên ~[a, b]~, hãy đếm số lượng số chính phương có trong đoạn ~[a, b]~.

Input

Chứa hai số tự nhiên ~a, b~ cách nhau một dấu cách (~1 \le a \le b \le 10^9~).

Output

Số ~d~ là số lượng số chính phương có trong đoạn ~[a, b]~.

Sample Input 1

1 5

Sample Output 1

2

1, 4 là các số chính phương.

Sample Input 2

10 20

Sample Output 2

1

16 là số chính phương

Sample Input 3

5 8

Sample Output 3

0

Subtasks

Từ là tập hợp các kí tự liên tiếp nhau trong bảng mã ASCII được viết cách nhau bởi dấu cách. Ví dụ cho xâu kí tự "lop 9b THCS" có ba từ "lop", "9b", "THCS".

Yêu cầu: Cho xâu ~S~ trong đó các kí tự được lấy từ tập {'0'..'9', 'A'..'Z', 'a'..'z'} và dấu cách, hãy đếm xem có bao nhiêu độ dài khác nhau của các từ có trong xâu.

Input

Có một dòng duy nhất chứa xâu ~S~ (có ít nhất một từ).

Output

• Dòng 1 ghi số dương ~d~ là số lượng độ dài khác nhau của các từ trong xâu;
• Dòng thứ ~i~ trong ~d~ dòng tiếp theo mỗi dòng ghi hai số ~x~ và ~y~, trong đó ~x~ là độ dài của từ và ~y~ là số từ có độ dài tương ứng là ~x~. Giá trị ~x~ trên mỗi dòng tăng dần theo độ dài của từ.

Sample Input 1

Ky thi HSG THCS 2026 

Sample Output 1

3
2 1
3 2
4 2

Có 3 độ dài khác nhau của các từ xuất hiện trong xâu:

• Các từ có độ dài 2: "Ky"
• Các từ có độ dài 3: "thi", "HSG"
• Các từ có độ dài 4: "THCS", "2026"

Subtasks

Có ~n~ hộp quà, các hộp quà được đánh số từ ~1~ đến ~n~, hộp thứ ~i~ có giá trị ~a_i (1 \le a_i \le m)~. Lớp Nam được cô giáo giao nhiệm vụ chuẩn bị ~K~ giỏ quà từ ~n~ hộp quà đã có, tuân thủ tất cả các quy tắc sau:

• Mỗi giỏ quà gồm hai hộp quà;
• Hộp quà thứ nhất được lấy từ các hộp quà có chỉ số từ ~1~ đến ~K~, hộp quà thứ 2 được lấy từ các hộp quà có chỉ số từ ~K+1~ đến ~n~;
• Hộp quà thứ nhất có giá trị nhỏ hơn hộp quà thứ 2.

Ví dụ: Cho các hộp quà có giá trị lần lượt như sau: 2 1 4 2 3 2 4 5 2 3. Nam có thể ghép được 4 hộp quà có giá trị ~\{1, 2, 2, 4\}~ với 6 hộp quà còn lại ~\{3, 2, 4, 5, 2, 3\}~ tạo thành 4 giỏ quà được ghép là ~\{(1, 2), (2, 3), (2, 3), (4, 5)\}~ hoặc ~\{(2, 3), (1, 2), (4, 5), (2, 4)\}~.

Yêu cầu: Cho ~n~ hộp quà có giá trị ~a_1, a_2, ..., a_n~, hãy tìm ~K~ lớn nhất theo quy tắc trên.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, m~ (~1 \le n \le 10^5, 1 \le m \le 10^9~);
• Dòng tiếp theo ghi ~n~ số nguyên dương ~a_i~ (~1 \le a_i \le m~). Các số trong tệp cách nhau bởi dấu cách.

Output

Số ~K~ lớn nhất tìm được, nếu không có nghiệm thì ghi ra -1.

Sample Input 1

10 5
2 1 4 2 3 2 4 5 2 3

Sample Output 1

4

Sample Input 2

5 6
5 4 2 1 2

Sample Output 2

-1

Sample Input 3

3 3
1 2 3

Sample Output 3

1

Subtasks

Cho dãy ~A~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Một đoạn con liên tiếp của dãy ~A~ là đoạn ~a_l, a_{l+1}, ..., a_r~ với ~1 \le l \le r \le n~, giá trị đoạn con là độ chênh lệch của giá trị lớn nhất và giá trị nhỏ nhất của đoạn con. Giá trị của dãy số là tổng giá trị tất cả các đoạn con liên tiếp của dãy. Ví dụ: Cho dãy số 2 4 1 ta có các đoạn con liên tiếp ~\{2\}, \{4\}, \{1\}, \{2, 4\}, \{4, 1\}, \{2, 4, 1\}~, giá trị dãy số là ~0 + 0 + 0 + (4-2) + (4-1) + (4-1) = 0 + 0 + 0 + 2 + 3 + 3 = 8~.

Yêu cầu: Với dãy số nguyên dương ~a_1, a_2, ..., a_n~ có ~n~ phần tử, hãy tính giá trị của dãy số.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~);
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^7~). Các số trong tệp cách nhau bởi dấu cách.

Output

Một số nguyên duy nhất là giá trị của dãy số.

Sample Input

3
2 4 1

Sample Output

8

Subtasks