Bạn được cung cấp một mảng chứa n số nguyên. Nhiệm vụ của bạn là xác định dãy con dài nhất tăng dần trong mảng, tức là dãy con dài nhất mà mọi phần tử đều lớn hơn phần tử trước đó. Một dãy con là một dãy có thể được dẫn xuất từ mảng bằng cách xóa một số phần tử mà không làm thay đổi thứ tự của các phần tử còn lại.

Đầu vào

Dòng đầu tiên chứa số nguyên n: kích thước của mảng.

Sau đó có n số nguyên x1, x2,…, xn: nội dung của mảng.

Giới hạn

1≤n≤2⋅10^5

1≤xi≤10^9

Đầu ra

In ra chiều dài của dãy con tăng dài nhất

Ví dụ :

Input 01

6
1 2 4 1 5 2

Output 01

4

Bạn được cung cấp một số nguyên n. Trên mỗi bước, bạn có thể trừ một trong các chữ số khỏi số. Cần thực hiện bao nhiêu bước để số đó bằng 0?

Đầu vào

Dòng duy nhất chứa số nguyên n

Giới hạn

1<=n<=10^6

Đầu ra

In ra số bước tối thiểu

Ví dụ :

Input 01

27

Output 01

5

Giải thích test :

Các bước thực hiện : 27→20→18→10→9→0

Bạn biết rằng một mảng có n số nguyên chỉ gồm các số từ 1 đến m và độ lệch giữa 2 phần tử liền kề trong mảng không được vượt quá 1 đơn vị.

Bài toán đặt ra đó là cho bạn một mảng trong đó một số giá trị trong mảng chưa được xác định giá trị, nhiệm vụ của bạn là đếm số mảng phù hợp với mô tả, đó là các số liền kề trong mảng không lệch nhau quá 1 đơn vị và các giá trị trong mảng chỉ được nằm trong đoạn từ 1 tới m.

Đầu vào

Dòng nhập đầu tiên có hai số nguyên n và m: kích thước mảng và giới hạn trên cho mỗi giá trị.

Dòng tiếp theo có n số nguyên a1, a2,…, an: nội dung của mảng. Giá trị 0 biểu thị một giá trị không xác định.

Giới hạn

1≤n≤10^5

1≤m≤100

0≤a[i]≤m

Đầu ra

In ra số lượng mảng phù hợp sau khi chia dư cho 1e9 + 7

Ví dụ :

Input 01

3 5
2 0 2

Output 01

3

Giải thích test :

Các mảng có thể thỏa mãn : [2, 1, 2], [2, 2, 2], [2, 3, 2]

Nhiệm vụ của bạn là đếm số cách các số 1,2,…, n có thể chia thành hai tập có tổng bằng nhau.

Các phần tử trong tập không xét đến thứ tự Ví dụ, nếu n = 7, có 4 nghiệm: {1,3,4,6} và {2,5,7}. {1,2,5,6} và {3,4,7}. {1,2,4,7} và {3,5,6}. {1,6,7} và {2,3,4,5}.

Đầu vào

Dòng duy nhất chứa số nguyên dương n

Giới hạn

1<=n<=500

Đầu ra

In ra kết quả sau khi chia dư với 10^9 + 7

Ví dụ :

Input 01

7

Output 01

4

Cho một hình chữ nhật a × b, nhiệm vụ của bạn là cắt nó thành các hình vuông.

Trên mỗi lần cắt, bạn có thể chọn một hình chữ nhật và cắt nó thành hai hình chữ nhật sao cho tất cả độ dài các cạnh vẫn là số nguyên. Số lần di cắt tối thiểu có thể là bao nhiêu?

Đầu vào

Dòng duy nhất chứa 2 số nguyên a và b.

Giới hạn

1<=a,b<=500

Đầu ra

In ra số lần cắt tối thiểu

Ví dụ :

Input 01

3 5

Output 01

3