Cho một dãy gồm ~n~ điểm ~a_1, a_2, \ldots, a_n~. Với mọi ~1 \le i < n~, dữ liệu đảm bảo ~|a_{i+1} - a_i| \le 1~.

Một đoạn ~[l, r]~ được gọi là gần như ổn định nếu chênh lệch giữa giá trị lớn nhất và giá trị nhỏ nhất của đoạn đó không vượt quá ~1~. Cụ thể, gọi ~M~ là giá trị lớn nhất và ~m~ là giá trị nhỏ nhất trong các ~a_i~ với ~l \le i \le r~; đoạn ~[l, r]~ gần như ổn định nếu ~M - m \le 1~.

Hãy tìm độ dài của đoạn gần như ổn định dài nhất.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~n~ — số lượng điểm.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ — mô tả dãy điểm.

Kết quả

In ra một số nguyên duy nhất là độ dài của đoạn gần như ổn định dài nhất.

Ví dụ

Đầu vào:

5
1 2 3 2 3

Đầu ra:

4

Giải thích: Đoạn ~[2, 5]~ gồm các điểm ~2, 3, 2, 3~ có giá trị lớn nhất ~3~ và nhỏ nhất ~2~, chênh lệch ~1~ nên gần như ổn định. Không có đoạn gần như ổn định nào dài hơn ~4~.

Đầu vào:

11
5 4 5 5 6 7 8 8 8 7 6

Đầu ra:

5

Giải thích: Đoạn ~[6, 10]~ gồm các điểm ~7, 8, 8, 8, 7~ có chênh lệch ~1~ và dài ~5~.

Giới hạn

• ~2 \le n \le 10^5~
• ~1 \le a_i \le 10^5~
• ~|a_{i+1} - a_i| \le 1~ với mọi ~1 \le i < n~

Một số nguyên không âm ~a~ được gọi là số chính phương nếu tồn tại số nguyên không âm ~d~ sao cho ~a = d^2~. Chẳng hạn ~0, 1, 4, 36~ đều là số chính phương.

Cho dãy gồm ~n~ số nguyên không âm ~A_1, A_2, \ldots, A_n~. Hãy đếm số cặp chỉ số ~(i, j)~ thỏa mãn đồng thời hai điều kiện:

• ~1 \le i < j \le n~
• ~A_i \cdot A_j~ là một số chính phương.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~n~ — độ dài của dãy.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \ldots, A_n~.

Kết quả

In ra một số nguyên duy nhất là số cặp tìm được.

Ví dụ

Đầu vào:

5
0 3 2 8 12

Đầu ra:

6

Giải thích: Sáu cặp thỏa mãn là ~(1, 2), (1, 3), (1, 4), (1, 5), (2, 5), (3, 4)~. Ví dụ với cặp ~(2, 5)~ ta có ~A_2 \cdot A_5 = 3 \cdot 12 = 36 = 6^2~. Mọi cặp chứa ~A_1 = 0~ đều thỏa mãn vì tích bằng ~0 = 0^2~.

Đầu vào:

8
2 2 4 6 3 100 100 25

Đầu ra:

7

Giới hạn

• ~2 \le n \le 2 \cdot 10^5~
• ~0 \le A_i \le 2 \cdot 10^5~

Xâu ~20230322~ có thể sắp xếp lại thành ~02320232~, tức là xâu ~0232~ viết liền hai lần. Một xâu chỉ gồm các chữ số được gọi là may mắn nếu nó có thể sắp xếp lại thành (hoặc vốn đã là) một xâu nào đó viết liền hai lần.

Cho xâu ~S~ chỉ gồm các chữ số. Hãy đếm số cặp chỉ số ~(l, r)~ thỏa mãn đồng thời:

• ~1 \le l \le r \le |S|~, trong đó ~|S|~ là độ dài của ~S~;
• xâu con liên tiếp gồm các ký tự từ vị trí ~l~ đến vị trí ~r~ của ~S~ là xâu may mắn.

Dữ liệu vào

Một dòng duy nhất chứa xâu ~S~. Xâu ~S~ có thể bắt đầu bằng chữ số ~0~.

Kết quả

In ra một số nguyên duy nhất là số cặp tìm được.

Ví dụ

Đầu vào:

20230322

Đầu ra:

4

Giải thích: Bốn cặp thỏa mãn là ~(1, 6), (1, 8), (2, 7)~ và ~(7, 8)~.

Đầu vào:

0112223333444445555556666666777777778888888889999999999

Đầu ra:

185

Đầu vào:

3141592653589793238462643383279502884197169399375105820974944

Đầu ra:

9

Giới hạn

• ~1 \le |S| \le 5 \cdot 10^5~
• ~S~ chỉ gồm các chữ số từ ~0~ đến ~9~.

Kỳ nghỉ hè, Per rủ các bạn lập băng hải tặc để ra khơi tìm kho báu. Per đã tìm thấy một hòn đảo lý tưởng để tìm kiếm. Ban đầu thuyền đang ở điểm ~(x_1, y_1)~ (coi mặt biển là mặt phẳng tọa độ ~Oxy~) và Per muốn di chuyển đến hòn đảo ở điểm ~(x_2, y_2)~.

Per biết trước dự báo thời tiết: xâu ~s~ độ dài ~n~ chỉ gồm các chữ cái ~U~, ~D~, ~L~, ~R~, mỗi ký tự ứng với một hướng gió. Dự báo có tính chu kỳ: ngày thứ nhất gió thổi theo ~s_1~, ngày thứ hai theo ~s_2~, ..., ngày thứ ~n~ theo ~s_n~, ngày thứ ~n + 1~ lại theo ~s_1~, và cứ thế lặp lại.

Gió đẩy thuyền như sau:

• gió ~U~: thuyền đi từ ~(x, y)~ đến ~(x, y + 1)~;
• gió ~D~: thuyền đi từ ~(x, y)~ đến ~(x, y - 1)~;
• gió ~L~: thuyền đi từ ~(x, y)~ đến ~(x - 1, y)~;
• gió ~R~: thuyền đi từ ~(x, y)~ đến ~(x + 1, y)~.

Mỗi ngày, ngoài gió, thuyền còn có thể tự đi ~1~ đơn vị theo một trong bốn hướng trên hoặc đứng yên. Vị trí cuối ngày là tổng của hướng gió và hướng thuyền tự đi. Ví dụ, nếu gió thổi hướng ~U~ còn thuyền đi hướng ~L~ thì từ ~(x, y)~ thuyền tới ~(x - 1, y + 1)~; nếu thuyền cũng đi hướng ~U~ thì nó tới ~(x, y + 2)~.

Hãy giúp Per xác định số ngày ít nhất để thuyền tới được hòn đảo.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~x_1, y_1~ — tọa độ ban đầu của con thuyền.
• Dòng thứ hai chứa hai số nguyên ~x_2, y_2~ — tọa độ của hòn đảo. Dữ liệu đảm bảo hai tọa độ này khác nhau.
• Dòng thứ ba chứa một số nguyên ~n~ — độ dài của xâu ~s~.
• Dòng thứ tư chứa xâu ~s~ chỉ gồm các chữ cái ~U~, ~D~, ~L~, ~R~.

Kết quả

In ra số ngày ít nhất để Per tới được hòn đảo ở tọa độ ~(x_2, y_2)~. Nếu không thể tới được, in ra ~-1~.

Ví dụ

Đầu vào:

0 0
3 5
3
UDU

Đầu ra:

6

Giải thích: Thuyền tự đi theo dãy hướng ~RRRUUU~. Tọa độ thay đổi lần lượt là ~(0, 0) \to (1, 1) \to (2, 0) \to (3, 1) \to (3, 3) \to (3, 3) \to (3, 5)~.

Đầu vào:

0 0
0 2
1
R

Đầu ra:

-1

Giải thích: Con thuyền không bao giờ tới được hòn đảo.

Giới hạn

• ~0 \le x_1, y_1 \le 10^9~
• ~0 \le x_2, y_2 \le 10^9~
• ~(x_1, y_1) \ne (x_2, y_2)~
• ~1 \le n \le 10^5~