Cho một dãy \(n\) số nguyên. Hỏi ta cần xoá đi ít nhất bao nhiêu số hạng để các số còn lại (giữ nguyên thứ tự) tạo thành một dãy số tăng dần (với ít nhất hai số hạng)? Viết chương trình xác định giá trị đó. Nếu không có cách xoá thoả mãn, in ra kết quả là \(-1\).

Input Specification

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên dương \(n\),
• Dòng thứ hai chứa dãy \(n\) số nguyên, hai số liên tiếp ngăn cách nhau bởi một dấu khoảng trắng.

Output Specification

In ra kết quả trên một dòng.

Constraints

• \(n \leq 10^4\);
• Mỗi phần tử có giá trị tuyệt đối không quá \(10^6\).

Input Sample

5
1 4 3 2 5

Output Sample

2

Một vương quốc nọ sử dụng tiền xu với \(N\) mệnh giá khác nhau, lần lượt là \(v_1\), \(v_2\), \(v_3\), ..., \(v_n\) (đồng). Tỉ phú Umbala là một người vô cùng giàu có, đến mức ông ta có đủ vô vàn số lượng tiền xu mỗi mệnh giá.

Sắp tới, Umbala muốn tới thành phố ViFa để mua một chiếc xe ô tô, với giá là \(P\) đồng. Để xếp gọn hành lý, ông ta muốn mang số đồng xu ít nhất có thể, nhưng phải vừa đủ để trả tiền mua xe ô tô - không thừa, không thiếu.

Em hãy viết chương trình tính số đồng xu nhỏ nhất mà Umbala phải mang theo. Nếu không có cách mang theo các đồng xu thoả mãn yêu cầu thì in ra \(-1\).

Input Specification

Gồm ba dòng:

• Dòng thứ nhất chứa số nguyên dương \(N\);
• Dòng thứ hai chứa dãy \(N\) số nguyên dương đôi một khác nhau, hai số liên tiếp ngăn cách nhau bởi một dấu khoảng trắng;
• Dòng thứ ba chứa số nguyên dương \(P\).

Output Specification

In ra kết quả trên một dòng.

Constraints

• \(n \leq 10^3\)
• \(v_i \leq 10^4\)
• \(P \leq 10^5\)

Input Sample

3
1 3 5
11

Output Sample

3

Explanation for Sample Output

Umbala có thể mang theo các đồng tiền (1, 5, 5) hoặc (3, 3, 5).

Cho một hàng có \(n\) quả bóng màu trắng, được đánh số thứ tự lần lượt từ \(1\) đến \(n\). Alice tô mỗi quả bóng bởi một trong ba màu xanh, đỏ, vàng sao cho không có hai quả bóng nào cạnh nhau cùng được tô màu đỏ.

Viết chương trình tính số khả năng khác nhau về thứ tự màu của dãy bóng mà Alice sẽ tô. Nếu kết quả có giá trị lớn thì đưa ra giá trị theo modulo \(10^9 + 7\).

Input Specification

Gồm số nguyên dương \(n\) được ghi trên một dòng duy nhất.

Output Specification

In ra kết quả trên một dòng.

Constraints

\(n \leq 10^6\)

Input Sample

2

Output Sample

8

Ở xứ sở nọ, giá vàng thay đổi liên tục theo ngày và kì lạ là giá bán, giá mua luôn bằng nhau. Tỉ giá luôn có dạng 1 thỏi vàng = \(x\) (đồng) với \(x\) là một số nguyên dương.

Một hôm, Dobita ngủ mơ thấy mình được đi đến tương lai và biết được tỉ giá vàng trong thời gian \(n\) ngày tiếp theo. Sau đó, bạn ấy quyết định sẽ mua 1 thỏi vàng rồi bán để đạt được lợi nhuận tốt nhất trong chuỗi \(n\) ngày đó.

Em hãy viết chương trình xác định xem Dobita có thể đạt lợi nhuận cao nhất là bao nhiêu đồng cho việc mua - bán một thỏi vàng.

Input Specification

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên dương \(n\),
• Dòng thứ hai chứa dãy \(n\) số nguyên dương, tương ứng là giá trị 1 thỏi vàng (tính theo đồng) trong các ngày, hai số liên tiếp ngăn cách nhau bởi một dấu khoảng trắng.

Output Specification

In ra kết quả trên một dòng.

Constraints

• \(n \leq 10^5\);
• Một thỏi vàng có giá trị không quá \(10^4\) đồng.

Input Sample

6
7 1 5 3 6 4

Output Sample

5

Explanation for Sample Output

Dobita đạt được lợi nhuận lớn nhất nếu mua ở ngày 2 (giá 1 đồng) và bán ở ngày 5 (giá 6 đồng).