USACO 2013 - Tháng 3 - Hạng Bạc

Bessie và những người bạn đang chơi một phiên bản poker đặc biệt với một bộ bài có \(N\) (\(1 \le N \le 100\,000\)) hạng khác nhau, được đánh số thuận tiện từ \(1\) đến \(N\) (một bộ bài thông thường có \(N = 13\)). Trong trò chơi này, chỉ có một loại bộ bài mà những con bò có thể đánh: người chơi có thể chọn một lá bài mang số \(i\) và một lá bài mang số \(j\), rồi đánh một lá thuộc mỗi giá trị từ \(i\) đến \(j\). Loại bộ bài này được gọi là một "sảnh".

Trên tay Bessie hiện có \(a_i\) lá bài hạng \(i\) (\(0 \le a_i \le 100000\)). Hãy giúp cô tìm số sảnh ít nhất phải đánh để loại bỏ tất cả các lá bài của mình.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\).

Dòng thứ \(i+1\) trong \(N\) dòng tiếp theo chứa giá trị \(a_i\).

Dữ liệu ra

In ra số sảnh ít nhất Bessie phải đánh để loại bỏ tất cả các lá bài của mình.

Ví dụ

5
2
4
1
2
3

6

Nguồn

USACO 2013 March Contest, Silver — Problem 1: Poker Hands

Tác giả đề: Albert Gu, 2011.

Sau nhiều mùa đông khắc nghiệt, Farmer John quyết định đã đến lúc sơn lại trang trại. Trang trại gồm \(N\) khu vực có hàng rào bao quanh (\(1 \le N \le 50\,000\)), mỗi khu vực có thể được mô tả bởi một hình chữ nhật trên mặt phẳng hai chiều với các cạnh song song với trục \(x\) và trục \(y\). Một khu vực có thể nằm trong một khu vực khác, nhưng không có hai hàng rào nào giao nhau. Vì thế, nếu hai khu vực phủ lên cùng một phần của mặt phẳng hai chiều thì một khu vực phải nằm bên trong khu vực còn lại.

FJ nhận thấy rằng một khu vực nằm bên trong một khu vực khác sẽ không thể được nhìn thấy từ thế giới bên ngoài, nên ông chỉ muốn sơn lại những khu vực không nằm bên trong bất kỳ khu vực nào khác. Hãy giúp FJ xác định tổng số khu vực ông cần sơn.

Dữ liệu vào

Dòng đầu tiên chứa số khu vực \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo mô tả một khu vực bằng 4 số nguyên \(x1\), \(y1\), \(x2\) và \(y2\) cách nhau bởi dấu cách, trong đó \((x1,y1)\) là góc dưới bên trái và \((x2,y2)\) là góc trên bên phải của khu vực. Tất cả các tọa độ đều nằm trong khoảng từ 0 đến \(1\,000\,000\).

Dữ liệu ra

In ra số khu vực không nằm bên trong những khu vực khác.

Ví dụ

3
2 0 8 9
10 2 11 3
4 2 6 5

2

Nguồn

USACO 2013 March Contest, Silver — Problem 2: Farm Painting

Tác giả đề: Brian Dean, 2013.

Oanh Trúc Béo muốn đi phát quà liên khối cho \(n\) học sinh khối chuyên Tin. Các học sinh này đều đứng trên trục số và được đánh số lần lượt từ \(1\) đến \(n\), học sinh thứ \(i\) đứng ở tọa độ \(p_i\). Oanh Trúc đứng ở gốc tọa độ (điểm \(0\)) và muốn tìm một trình tự phát quà để tổng độ bất mãn của \(n\) học sinh này là nhỏ nhất có thể, biết rằng Oanh Trúc cần đúng \(1\) phút để di chuyển được một đơn vị độ dài trên trục số, đồng thời, nếu học sinh nào chưa được nhận quà, thì cứ mỗi phút trôi qua, độ bất mãn của bạn ấy sẽ tăng lên \(1\) (độ bất mãn ban đầu của mỗi người đều bằng \(0\)).

Các bạn hãy lập trình tính toán giúp Oanh Trúc độ bất mãn nhỏ nhất có thể nhé!

Input

• Dòng đầu chứa số nguyên dương \(n\) \((n\leq 1000)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(p_1\), \(p_2\),..., \(p_n\) \(\left(-5\cdot 10^5\leq p_i\leq 5\cdot 10^5\right)\).

Output

• Tổng độ bất mãn nhỏ nhất có thể.

Example

4
-2 -12 3 7

50