Sắp xếp là một trong những thuật toán phổ biến nhất trong khoa học máy tính. An vừa được giới thiệu các thuật toán sắp xếp và biết rằng thuật toán sắp xếp nhanh (Quick Sort) có độ phức tạp trung bình là ~O(n \log{n})~. Tuy nhiên An vẫn muốn sáng tạo một thuật toán sắp xếp mới và xem thử liệu nó có tốt hơn Quick Sort. Xét một mảng ~n~ số nguyên, mỗi phần tử có giá trị từ ~1~ đến ~n~ và mỗi giá trị chỉ xuất hiện một lần trong mảng. Thuật toán này sẽ sắp xếp mảng trên trong ~n~ bước như sau:

• Bước 1: phần tử có giá trị ~1~ sẽ được chuyển đến vị trí ~1~ bằng cách liên tiếp hoán đổi vị trí với phần tử liền kề với nó.

• Bước 2: phần tử có giá trị ~n~ sẽ được chuyển đến vị trí ~n~ bằng cách như bước ~1~.

• Bước 3: phần tử có giá trị ~2~ sẽ được chuyển đến vị trí ~2~ bằng cách tương tự.

• Bước 4: phần tử có giá trị ~n - 1~ sẽ được chuyển đến vị trí ~n - 1~ bằng cách tương tự.

• Và cứ thể tiếp tục đến bước ~n~.

Tổng quát hơn, ở bước lẻ, An sẽ chọn phần tử có giá trị nhỏ nhất chưa được sắp xếp và di chuyển phần tử này đến vị trí đúng của nó. Ở bước chẵn An sẽ chọn phần tử có giá trị lớn nhất chưa được sắp xếp và di chuyển phần tử này đến vị trí đúng của nó.

Yêu cầu: Viết chương trình cho biết số lần hoán đổi vị trí các phần tử tại mỗi bước của thuật toán trên.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ cho biết số lượng phần tử của mảng.

• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên ~a_i~ ~(1 \leq a_i \leq n)~ cho biết giá trị của phần tử thứ ~i~ trong mảng. Các giá trị ~a_i~ không lặp lại.

Output

• Gồm ~n~ số nguyên, số thứ ~i~ cho biết số lần hoán đổi vị trí các phần tử ở bước thứ ~i~ của thuật toán. Mỗi số ghi trên một dòng.

Scoring

Sample Input 1

7
5
2
6
7
3
1
4

Sample Output 1

5
2
1
2
1
1
0

Bắn tàu là trò chơi khá phổ biến và có nhiều phiên bản. Hãy cùng xét một phiên bản của trò chơi này. Có ~N~ tàu của địch đang hoạt động ngoài khơi được đánh số từ ~1~ đến ~N~, tàu thứ ~i~ luôn cách bờ một khoảng ~d_i~.

Nhiệm vụ của người chơi là phải phá hủy hết các tàu theo thứ tự tàu ~1~, tàu ~2~, ... đến tàu ~N~. Người chơi được cung cấp vũ khí là một loại ngư lôi, ban đầu có thể được thiết lập ở bất kỳ mức năng lượng nào và trong quá trình chơi được thay đổi qua một mức năng lượng bất kỳ tối đa ~K~ lần ~(1 \leq K < N)~.

Nếu được thiết lập ở mức năng lượng ~R~ thì khi bắn ngư lôi có thể phá hủy một tàu cách bờ trong phạm vi nhỏ hơn hay bằng ~R~ đơn vị chiều dài. Ở lần bắn tàu thứ ~i~, nếu khoảng cách ~d_i~ nhỏ hơn mức năng lượng hiện tại ~R~ của ngư lôi thì người chơi bị trừ một số điểm là ~R - d_i~ (vì sử dụng lãng phí năng lượng).

Viết chương trình cho biết số điểm bị trừ ít nhất sau khi người chơi phá hủy hết ~N~ tàu.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ cho biết số lượng tàu và số lần tối đa đổi mức năng lượng của ngư lôi.

Dòng thứ 2 chứa ~N~ số nguyên, số thứ ~i~ cho biết ~d_i~ ~(0 \leq d_i \leq 10^6)~ là khoảng cách tới bờ của tàu thứ ~i~.

Output

Một số nguyên duy nhất là số điểm bị trừ ít nhất sau khi người chơi phá hủy hết ~N~ tàu.

Sample Input 1

7 1
80 10 5 7 100 20 35

Sample Output 1

313

Sample Input 2

7 2
80 10 5 7 100 20 35

Sample Output 2

153

Scoring

Notes

Test 1:

Ban đầu ngư lôi có mức năng lượng là 100.

Sau lần bắn thứ 5, thay đổi năng lượng về mức 35.

Test 2:

Ban đầu ngư lôi có mức năng lượng là 80.

Sau lần bắn thứ 1, thay đổi năng lượng về mức 10.

Sau lần bắn thứ 4, thay đôi năng lượng về mức 100.

Bờm được thuê lát gạch mặt sàn một quảng trường bằng các viên gạch hình chữ nhật có kích thước khác nhau. Mặt sàn có thể được xem là một lưới các ô vuông, vị trí các điểm trên mặt sàn được xác định bằng hệ tọa độ Descartes. Bờm đặt các viên gạch không theo thứ tự nào nhưng cẩn thận đặt góc của viên gạch trùng với điểm trên mặt sàn và cạnh của gạch thì song song với trục tọa độ (trục hoành và trục tung). Các viên gạch có thể tiếp xúc nhau nhưng không nằm chồng lên nhau. Vì không đặt gạch theo thứ tự nên sau khi lát được ~N~ viên gạch thì Bờm đã tạo ra nhiều khu vực đã lát gạch. Một khu vực đã lát gồm các viên gạch có cạnh tiếp xúc nhau hoặc có chung góc. Ông chủ chỉ trả tiền cho một khu vực đã lát nên Bờm muốn tìm khu vực có diện tích lớn nhất để tính công.

Yêu cầu: Viết một chương trình tính diện tích khu vực đã lát gạch lớn nhất.

Input

Dòng đầu tiên chứa một số nguyên dương ~N~ cho biết số viên gạch Bờm đã lát.

~N~ dòng tiếp theo mô tả vị trí và kích thước của các viên gạch đã lát. Mỗi dòng chứa 4 số nguyên ~X, Y, D, C~ với (~X, Y~) là tọa độ của góc dưới bên trái viên gạch trên mặt sàn và ~D~ là chiều dài (độ lớn của cạnh song song với trục hoành), ~C~ là chiều cao (độ lớn của cạnh song song với trục tung) của viên gạch.

Ràng buộc: Tất cả các test có giá trị ~X, Y~, diện tích khu vực đã lát trong giới hạn số nguyên có dấu 32 bit và ~0 \lt D, C \le 500~.

Output

In ra một số nguyên cho biết diện tích khu vực đã lát gạch lớn nhất.

Scoring

Sample Input 1

6
6 4 3 1
6 1 1 1
4 7 1 1
3 3 1 2
4 6 2 1
4 1 2 2

Sample Output 1

7