Độ khó: Dễ (1/4 điểm)

Dọc theo một con đường thẳng người ta trồng một hàng gồm $n$ cây xanh có khoảng cách đều nhau. Để trang trí cho con đường vào ban đêm, người ta gắn lên hàng cây một số bóng đèn theo quy tắc xen kẽ, cứ hai cây liền kề nhau thì một cây được gắn đèn, một cây không gắn đèn. Biết rằng để gắn một bóng đèn lên một cây thì cần chi phí với số tiền là $x$ đồng.

Yêu cầu: Hãy tính tổng chi phí để gắn được nhiều bóng đèn nhất cho hàng cây.

Input

Một dòng gồm hai số nguyên $n$ và $x$ cách nhau một dấu cách $(1 \le n \le 10^9;\ 1 \le x \le 10^3)$.

Output

Một số nguyên là kết quả.

Lưu ý: Tuy đề bài gốc yêu cầu dữ liệu với file (TRANGTRI.INP, TRANGTRI.OUT) nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

5 10

Sample Output 1

30

Độ khó: Trung bình (2/4 điểm)

Tí là tổng giám đốc một công ty lớn có rất nhiều đối tác làm ăn. Hôm nay một đối tác yêu cầu Tí phải chuyển cho họ một số tiền $d$ qua chi phiếu. Trợ lý báo rằng bàn phím máy tính in chi phiếu đã hỏng mất phím số $4$ nên không thể in được số tiền trong chi phiếu vì giá trị của số tiền có chữ số $4$.

Tí là người thông minh nên đã gợi ý cho trợ lý khắc phục bằng cách in thành hai tờ sao cho tổng số tiền ghi trên hai tờ cộng lại đúng bằng $d$ và giá trị tiền trên hai tờ lệch nhau ít nhất có thể.

Yêu cầu: Hãy giúp trợ lý tính số tiền cần in trên hai tờ chi phiếu theo yêu cầu của Tí.

Input

Chỉ ghi số nguyên dương $d$ $(d \le 10^6)$.

Output

Hai số nguyên thỏa yêu cầu (không chứa chữ số $4$), số nhỏ in trước số lớn in sau, cách nhau một dấu cách.

Lưu ý: Tuy đề bài gốc yêu cầu dữ liệu với file (INSEC.INP, INSEC.OUT) nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

489

Sample Output 1

239 250

Độ khó: Trung bình (2/4 điểm)

Độ lân cận của một số $x$ với một số $y$ được tính bằng công thức: $d(x, y) = |x - y|$. Độ lân cận của một số với dãy số là độ lân cận nhỏ nhất của số đó với các số khác trong dãy. Ví dụ, dãy gồm $4$ số ${3, 8, 2, 10}$ thì độ lân cận của số $3$ với ba số trong dãy ${8, 2, 10}$ là $d(3, 8) = 5$; $d(3, 2) = 1$; $d(3, 10) = 7$. Do vậy độ lân cận của $3$ với dãy số đã cho là $1$.

Cho một dãy gồm $n$ số nguyên $a1, a2, \ldots, a_n$.

Yêu cầu: Hãy tính tổng độ lân cận của các số trong dãy số.

Input

• Dòng 1: số nguyên $n$ $(3 \le n \le 10^5)$.
• Dòng 2: $n$ số nguyên $a1, a2, \ldots, an$ $(1 \le ai \le 10^6)$.

Output

Một số nguyên duy nhất là tổng độ lân cận.

Lưu ý: Tuy đề bài gốc yêu cầu dữ liệu với file (LANCAN.INP, LANCAN.OUT) nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

4
3 8 2 10

Sample Output 1

6

Giải thích: độ lân cận của $3$ với ${8, 2, 10}$ là $1$; của $8$ với ${3, 2, 10}$ là $2$; của $2$ với ${3, 8, 10}$ là $1$; của $10$ với ${3, 8, 2}$ là $2$. Tổng $1 + 2 + 1 + 2 = 6$.

Độ khó: Dễ (1/4 điểm)

Một dây chuyền sản xuất thiết bị vừa sản xuất được $n$ sản phẩm và đã dán nhãn cho mỗi sản phẩm một mã số để tiện quản lý. Mã số được dán cho mỗi sản phẩm là một số nguyên dương và không được có hai sản phẩm bất kỳ nào có mã số trùng nhau. Không may là dây chuyền dán nhãn bị lỗi nên trong những sản phẩm đã dán nhãn có thể có nhiều sản phẩm được dán cùng một nhãn (có mã số giống nhau).

Yêu cầu: Hãy tìm xem trong $n$ sản phẩm đã dán nhãn có ít nhất bao nhiêu sản phẩm cần dán lại để tất cả các sản phẩm đều có mã số khác nhau.

Input

• Dòng 1: số nguyên dương $n$ $(1 \le n \le 10^6)$.
• Dòng 2: $n$ số nguyên dương cách nhau một dấu cách là nhãn của $n$ sản phẩm, mỗi nhãn không vượt quá $10^7$.

Output

Một số nguyên là số lượng ít nhất sản phẩm cần dán lại nhãn.

Lưu ý: Tuy đề bài gốc yêu cầu dữ liệu với file (DANNHAN.INP, DANNHAN.OUT) nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

7
1 2 2 4 2 5 1

Sample Output 1

3

Giải thích: cần dán lại một nhãn có mã số $1$ và $2$ nhãn có mã số $2$, nên ít nhất $3$ sản phẩm.