Sample Input

5
5 3 2 3 6

Sample Output

0 5
1 5
2 4
1 5
0 0

Đề bài

Cho dãy số nguyên ~a_1, a_2, \dots, a_n~ (~0 \leq a_i \leq 10^9~, ~1 \leq n \leq 10^6~). Với dãy số nguyên này ta có thể thực hiện phép xử lý ~Reduce(i)~ thay thế 2 phần tử ~a_i~ và ~a_{i+1}~ bằng ~\max(a_i, a_{i+1})~ với chi phí là ~\max(a_i, a_{i+1})~. Sau ~n - 1~ lần thực hiện phép xử lý trên, ta được dãy số độ dài ~1~. Chi phí biến đổi dãy được tính bằng tổng chi phí của tất cả các phép xử lý đã thực hiện.

Yêu cầu: Cho ~n~ và các số ~a_i~, hãy xác định chi phí nhỏ nhất đưa dãy về độ dài ~1~.

Input

• Dòng đầu tiên chứa số nguyên ~n~.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa số nguyên ~a_i~.

Output

• Đưa ra một số nguyên — chi phí biến đổi tìm được.

Ví dụ

Sample Input

3
1
2
3

Sample Output

5

Giới hạn

• Thời gian: 1.0s
• Bộ nhớ: 256M

Đề bài

Nông dân John có ~N~ con bò sữa (~1 \leq N \leq 50000~) được nuôi trong một cái chuồng một chiều dài. Con bò thứ ~i~ đứng ở vị trí ~x_i~ và có chiều cao là ~h_i~ (~1 \leq x_i, h_i \leq 10^9~).

Một con bò sẽ cảm thấy "chật chội" nếu như có ít nhất một con bò khác có chiều cao lớn hơn hoặc bằng hai lần chiều cao của nó nằm trong khoảng cách ~D~ về bên trái và có ít nhất một con bò nữa có chiều cao lớn hơn hoặc bằng hai lần nó nằm trong khoảng cách ~D~ về bên phải (~1 \leq D \leq 10^9~).

Những con bò cảm thấy "chật chội" sẽ cho ra rất ít sữa. Chính vì vậy mà FJ muốn biết có bao nhiêu con bò cảm thấy "chật chội". Viết chương trình thực hiện điều này.

Input

Dữ liệu vào từ file văn bản CROWDED.INP:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~D~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i, h_i~ lần lượt là vị trí đứng và chiều cao của con bò thứ ~i~.

Output

Ghi ra file văn bản CROWDED.OUT một số nguyên duy nhất là số lượng con bò cảm thấy "chật chội".

Ví dụ

Sample Input

6 4
10 3
6 2
5 3
9 7
3 6
11 2

Sample Output

2

Giới hạn

• Thời gian: ~1.0s~
• Bộ nhớ: ~256MB~

Xét dãy số nguyên ~A=(a_1,a_2,\dots,a_n)~. Dãy chứa các phần tử ở các vị trí liên tiếp của ~A~ được gọi là dãy con. Hai dãy con được gọi là khác nhau nếu tồn tại ít nhất một vị trí mà phần tử của ~A~ ở vị trí đó tham gia vào dãy con này và không tham gia vào dãy con kia.

Yêu cầu: Cho số nguyên ~b~. Hãy xác định số lượng dãy con có giá trị lớn nhất của các phần tử trong dãy con đúng bằng ~b~.

Input:

Vào từ file văn bản NUMMAX.INP gồm:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~b~ ~(2 \le n \le 10^5;\ 1 \le b \le 10^9)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,\dots,a_n~ ~(1 \le a_i \le 10^9;\forall i \in [1;n])~

Output:

Ghi ra file văn bản NUMMAX.OUT một số nguyên duy nhất là số lượng dãy con tìm được.

Ví dụ:

NUMMAX.INP

4 5
1 3 5 2

NUMMAX.OUT

6

Subtask:

• Có ~20\%~ số test tương ứng ~20\%~ số điểm có ~n \le 10^3~ và không có dãy con thỏa mãn.
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~n \le 10^3~, đồng thời số ~b~ xuất hiện đúng ~1~ lần trong dãy và là số lớn nhất trong dãy đó.
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~n \le 5.10^3~
• ~40\%~ số test còn lại tương ứng ~40\%~ số điểm không có ràng buộc gì thêm.

Sample Input

9 2 3
40 -40 0 3 -5 0 3 0 1

Sample Output

4

Sample Input

5
3 1
1 2
5 2
0 1
5 4

Sample Output

YES
NO
YES
NO
YES

Đề bài

Sau thương vụ bản quyền phát sóng ~WC~ 2018, để tăng thêm uy tín, đồng thời quảng bá thêm hình ảnh, đài truyền hình ~ATA~ muốn lắp đặt thêm ~k~ màn hình ~LED~ (SMD và DIP) cỡ lớn để phục vụ người dân xem ~ASIAD~ tại các trạm nghỉ khác nhau trên quốc lộ từ ~HN~ tới ~SG~.

Qua khảo sát, có tất cả ~n~ trạm nghỉ, trạm nghỉ thứ ~i~ cách ~HN~ ~d_i~ km. Vì trục đường dài nên các màn hình phải thỏa mãn điều kiện là khoảng cách giữa hai màn hình liền tiếp trên đường, cũng như khoảng cách từ ~HN~ hoặc ~SG~ tới màn hình gần nhất phải không nhỏ hơn ~L~ km và không lớn hơn ~R~ km.

Màn hình thứ ~i~ được xây dựng có một hệ số hiệu quả ~T_i~ là tổng các khoảng cách từ quán đó đến những quán còn lại. ~T_i~ càng lớn thì giá trị phục vụ của quán đó càng cao. Vấn đề đặt ra là phải chọn ra ~k~ điểm sao cho tổng các ~T_i~ (giá trị phục vụ chung) là lớn nhất.

Yêu cầu: Cho ~n, k~, khoảng cách giữa ~HN~ và các trạm nghỉ, khoảng cách từ ~HN~ tới ~SG~. Hãy xác định giá trị phục vụ chung lớn nhất có thể đạt được. Dữ liệu đảm bảo có phương án.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ ~(1 \leq k \leq n \leq 5000)~.
• Dòng thứ hai chứa ~2~ số ~L~ và ~R~ ~(1 \leq L \leq R \leq 10^9)~.
• Dòng thứ ba chứa số nguyên dương không vượt quá ~10^9~ là khoảng cách giữa ~HN~ và ~SG~.
• Dòng thứ tư chứa ~n~ số nguyên, số thứ ~i~ xác định khoảng cách từ ~HN~ tới trạm nghỉ thứ ~i~, các số được đưa theo thứ tự tăng dần, không có hai trạm nghỉ nào cùng một địa điểm.

Output

• In ra một số nguyên — giá trị phục vụ chung lớn nhất.

Ví dụ

Sample Input

5 3
20 70
195
30 70 90 135 170

Sample Output

420

Giải thích ví dụ

Đặt ~3~ vị trí ~1, 3, 4~ ~(30, 90, 135)~ với hệ số hiệu quả:

~(90 - 30) + (135 - 30) + (90 - 30) + (135 - 90) + (135 - 30) + (135 - 90) = 420~

Giới hạn

• Thời gian: ~1.0s~
• Bộ nhớ: ~256MB~

Nguồn: Idol Nguyễn Văn Híu