Có \(n + 1\) đội bóng, các đội được đánh số từ \(0\) đến \(n\). Đội bóng số \(0\) dự định tổ chức một giải giao hữu và mời \(n\) đội tham gia. Khi tham gia, đội thứ \(i\) \((1 \le i \le n)\) dự định thi đấu đúng \(s_i\) \((1 \le s_i \le n)\) trận. Gọi \(s_0\) là số trận mà đội số \(0\) sẽ thi đấu, dựa vào số liệu đăng kí của mỗi đội, đội số \(0\) muốn biết \(s_0\) có thể nhận những giá trị nào để có thể tổ chức giải đấu với số lượng trận đúng như các đội đã đăng kí mà mỗi cặp đội sẽ đấu với nhau không quá một trận.

Yêu cầu: Cho các số nguyên dương \(s_1, s_2, ..., s_n\), hãy đếm xem có bao nhiêu giá trị nguyên dương \(s_0\) thỏa mãn.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(s_1, s_2, \dots, s_n\).

Output

• Ghi ra một số nguyên là số lượng giá trị \(s_0\) thỏa mãn.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \le 5\).
• Subtask \(2\) (\(15\%\) số điểm): \(n \le 50\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 500\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 5000\).
• Subtask \(5\) (\(15\%\) số điểm): \(n \le 50000\).
• Subtask \(6\) (\(15\%\) số điểm): \(n \le 500000\).

Example

2
2 2

1

Trên một khoảng sân rộng có chiều dài \(L\), người ta đặt một số thùng hàng. Dưới đây là một hình ảnh về sân có chiều dài 10, có chứa 5 thùng hàng A, B, C, D, E.

Hoàng muốn di chuyển các thùng hàng để tạo ra một khoảng sân có độ rộng tối thiểu là \(W\) để có thể chơi bóng cùng các bạn của mình. Mỗi bước, Hoàng có thể di chuyển một thùng hàng sang trái hoặc sang phải nếu vị trí vẫn nằm trong sân và vị trí đó còn trống.
Với ví dụ trên, khi Hoàng cần một khoảng sân độ rộng tối thiểu là \(3\), thì dưới đây là một cách di chuyển các thùng hàng. Cách di chuyển này cần \(2\) bước di chuyển.

Nếu Hoàng cần một khoảng sân độ rộng tối thiểu là \(4\), thì dưới đây là một cách di chuyển các thùng hàng. Cách di chuyển này cần \(4\) bước di chuyển.

Nếu Hoàng cần một khoảng sân độ rộng tối thiểu là \(5\), thì dưới đây là một cách di chuyển các thùng
hàng. Cách di chuyển này cần \(7\) bước di chuyển.

Yêu cầu: Cho vị trí ban đầu của các thùng hàng và giá trị \(W\), bạn hãy giúp Hoàng tính số bước di chuyển ít nhất.

Input

• Dòng đầu tiên ghi số \(T\) là số bộ dữ liệu \((T \le 10)\)
• \(T\) dòng tiếp theo, mỗi dòng mô tả một bộ dữ liệu. Mỗi dòng chứa một xâu kí tự \(s\) mô tả sân có độ dài không quá \(5 × 10^5\) và số nguyên dương \(W\) cách nhau bởi dấu cách. Xâu kí tự \(s\) chỉ gồm dấu chấm hoặc kí tự \(X\), trong đó kí tự chấm thể hiện vị trí sân không có thùng hàng và kí tự \(X\) thể hiện vị trí sân có thùng hàng.

Output

• Ghi ra \(T\) dòng, mỗi dòng chứa một số nguyên là ra số lần di chuyển các thùng hàng ít nhất.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(50\) và có không quá \(3\) thùng hàng.
• Subtask \(2\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(20\).
• Subtask \(3\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(50\).
• Subtask \(4\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(200\).
• Subtask \(5\) (\(25\%\) số điểm): độ dài xâu \(s\) không vượt quá \(5000\).
• Subtask \(6\) (\(20\%\) số điểm): độ dài xâu \(s\) không vượt quá \(50000\).
• Subtask \(7\) (\(15\%\) số điểm): không có ràng buộc gì thêm.

Example

4
.XX..XX.X. 2
.XX..XX.X. 3
.XX..XX.X. 4
.XX..XX.X. 5

0
2
4
7

Một công ty cung cấp dịch vụ mạng Internet đang thiết kế hệ thống mạng cho một khu dân cư. Vấn đề thiết kế được mô hình trên đồ thị như sau: Một đồ thị vô hướng có gồm \(n\) đỉnh và \(m\) cạnh, cạnh thứ \(t\) \((1 \le t \le m)\) nối đỉnh \(i_t\) đến đỉnh \(j_t\) \((1 \le i_t, j_t \le n; i_t ≠ j_t)\) có trọng số là số nguyên dương \(c(i_t, j_t)\), trong đó đỉnh \(1\) và đỉnh \(2\) là hai trạm cung cấp dịch vụ, các đỉnh \(i\) \((3 \le i \le n)\) là các trạm sử dụng dịch vụ. Công ty cần cần thiết kế các đường truyền nối, với mỗi đường truyền nối có hai đỉnh đầu cuối là đỉnh \(1\), đỉnh \(2\) và đi qua không quá \(k\) đỉnh sử dụng dịch vụ, cụ thể: Mỗi đường truyền nối xuất phát tại đỉnh \(1\), kết thúc tại đỉnh \(2\) và kết nối không quá \(k\) đỉnh sử dụng dịch vụ; Mỗi đỉnh \(i\) \((3 \le i \le n)\) là đỉnh sử dụng dịch vụ thuộc vào duy nhất một đường truyền nối; Độ dài đường truyền nối được tính bằng tổng trọng số các cạnh trên đường truyền nối.

Yêu cầu: Hãy thiết kế các đường truyền nối thỏa mãn điều kiện và tổng độ của các đường truyền nối là càng nhỏ càng nhất.

Input

• Dòng đầu chứa ba số nguyên \(n\), \(m\), \(k\) \((k + 2 \le n)\);
• Dòng thứ \(t\) \((1 \le t \le m)\) chứa ba số nguyên dương \(i_t\), \(j_t\), \(c(i_t, j_t)\), giá trị \(c_{ij}\) không vượt quá \(10^6\).

Output

• Dòng đầu ghi hai số nguyên \(w\) và \(s\) là tổng độ dài các đường truyền nối và số đường truyền nối được thiết kế;
• \(s\) dòng sau, mỗi dòng mô tả một đường truyền nối có dạng:
  • Dòng đầu ghi số \(d\) là lượng đỉnh trên đường truyền nối (bao gồm cả đỉnh \(1\) và \(2\));
  • \(d\) số tiếp theo, mỗi số mô tả đường truyền nối bắt đầu bằng \(1\) và kết thúc tại \(2\).

Scoring

• Subtask \(1\) (\(30\) điểm): \(n \le 10\).
• Subtask \(2\) (\(30\) điểm): \(n \le 18\).
• Subtask \(3\) (\(40\) điểm): \(n \le 30\).

Cách tính điểm:
Có \(20\) test, mỗi test \(5.0\) điểm. Gọi tổng độ dài các đường truyền nối của Ban giám khảo và thí sinh
tương ứng là \(w_{GK}\) và \(w_{TS}\), khi đó số điểm bạn đạt được cho mỗi test như sau:

• Nếu \(w_{TS}\) > 2 × \(w_{GK}\) thì thí sinh được 0 điểm;
• Nếu \(w_{TS}\) < \(w_{GK}\) thí sinh được 5 điểm;
• Nếu \(w_{GK}\) ≤ \(w_{TS}\) ≤ 2 × \(w_{GK}\) thí sinh được \(5.0 × (1 − \frac{w_{TS}−w_{GK}}{ w_{GK}})\)

Example

5 7 3
1 3 1
3 2 1
1 4 1
4 5 1
5 2 1
3 4 3
3 5 3

5 2
3 1 3 2
4 1 4 5 2