Bài 1. MMSEG – TÌM ĐOẠN CON

Description

Cho dãy số nguyên A = (a₁, a₂, …, aₙ).

Một đoạn con của dãy là dãy các phần tử liên tiếp: (aᵢ, aᵢ₊₁, …, aⱼ) với i ≤ j.
Độ dài đoạn con là j − i + 1.

Yêu cầu: Tìm độ dài nhỏ nhất của một đoạn con chứa đồng thời giá trị lớn nhất và giá trị nhỏ nhất của dãy A.

---

Input

• Dòng 1: số nguyên dương n (1 ≤ n ≤ 10⁵).
• Dòng 2: n số nguyên a₁, a₂, …, aₙ.

---

Output

• In ra một số nguyên duy nhất là độ dài đoạn con thỏa mãn yêu cầu.

---

Example

Input

8
1 3 6 2 8 1 3 8

Output

2

---

Bài 2. MSQUARE – HÌNH VUÔNG LỚN NHẤT

Description

Cho một bảng vuông kích thước n × n, mỗi ô chứa một số từ 1 đến 9.

Hãy tìm một hình vuông con thỏa mãn:

• Các cạnh song song với bảng ban đầu.
• Tất cả các ô trong hình vuông chỉ chứa một giá trị duy nhất.
• Cạnh hình vuông là lớn nhất có thể.

---

Input

• Dòng 1: số nguyên n (1 ≤ n ≤ 1000).
• n dòng tiếp theo, mỗi dòng gồm n số nguyên trong [1, 9].

---

Output

• In ra diện tích của hình vuông thỏa mãn yêu cầu.

---

Example

Input

8
1 3 6 2 8 1 3 8
1 2 2 2 2 2 2 2
2 2 2 2 2 3 7 8
3 2 2 2 2 1 2 3
4 5 6 7 8 2 2 2
2 4 2 1 4 2 2 2
1 2 3 4 5 6 7 8
6 5 4 3 6 5 4 1

Output

9

---

Bài 3. SUMC – TÍNH TỔNG

Description

Cho các số nguyên từ 1 đến n và hai số nguyên dương k, m.

Với mỗi i ≥ k, định nghĩa:

Cᵢ = (i − k + 1) × (i − k + 2) × … × i

Hãy tính:

S = Cₖ + Cₖ₊₁ + … + Cₙ

Do S rất lớn, chỉ cần in ra S mod m.

---

Input

• Một dòng chứa ba số nguyên n, k, m.

---

Output

• In ra S mod m.

---

Constraints

• n ≤ 10¹⁸
• k ≤ 500
• m ≤ 10¹⁸

---

Example

Input

6 3 1234

Output

210

Input

10 5 666013

Output

55440