Cho dãy số nguyên ~a~ gồm ~n~ phần tử. Hãy tìm cách chia dãy ~a~ ra thành ít dãy con (không nhất thiết liên tiếp) nhất, sao cho các dãy con đều là dãy không giảm và mỗi phần tử của ~a~ thuộc đúng một dãy con.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(n \le 10^5)~

• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~. (~a_i \le 10^9~)

  Output

• In ra số lượng dãy con ít nhất thỏa mãn.

Sample Test

Input:

4
1 5 4 6

Output:

2

Cho ~N~ đoạn gỗ, để xử lí chúng, ta cần:

• Thời gian xử lí đoạn gỗ đầu tiên là 1 phút.
• Sau khi xử lí xong đoạn gỗ có chiều dài ~l~ và trọng lượng ~w~, không mất thời gian xử lí nếu đoạn gỗ tiếp theo có chiều dài ~l'~ và trọng lượng ~w'~ thỏa mãn ~l \le l'~ và ~w \le w'~, ngược lại mất 1 phút để xử lí.

Tìm thời gian chuẩn bị ít nhất cho ~N~ đoạn gỗ.

Ví dụ có 5 đoạn: ~(9,4), (2,5), (1,2), (5,3), (4,1)~ thì thời gian ít nhất là 2 vì có thể xử lí theo thứ tự sau: ~(4,1), (5,3), (9,4), (1,2), (2,5)~.

Input

Dòng đầu là số lượng test ~T \le 100~, mỗi test gồm:

• Dòng đầu là số nguyên dương ~N \le 5000~.
• Sau đó ~N~ dòng tiếp theo gồm ~N~ cặp số nguyên dương ~(l_1,w_1), (l_2,w_2), ..., (l_N,w_N)~, ~l_i,w_i <= 10000~ là độ dài và trọng lượng khối gỗ.

Output

In ra T dòng, mỗi dòng là đáp án của test tương ứng.

Sample Test

Input:

3

5 
4 9 
5 2 
2 1 
3 5 
1 4

3 
2 2 
1 1 
2 2

3 
1 3 
2 2 
3 1

Output:

2
1
3

Trên hệ trục tọa độ ~OXY~, có ~n~ con robot, con robot thứ ~i~ ở tọa độ ~(x_i,y_i)~.

Giả sử một con robot đang ở vị trí ~(x,y)~, sau một giây, nó có thể đi tới ~4~ vị trí ~(x-1,y)~, ~(x,y-1)~, ~(x+1,y)~, ~(x,y+1)~.

Hãy tìm thời điểm ngắn nhất sao cho cả ~n~ con robot đều có thể cùng đứng ở một điểm nào đó trên hệ trục tọa độ.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ miêu tả số robot ~(1 \le n \le 3\times 10^5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của robot thứ ~i~ ~(|x_i|,|y_i| \le 10^{18})~.

Output

• In ra thời điểm nhanh nhất để các robot cùng đứng tại một điểm.

Sample Input 1

3
0 0
0 3
3 3

Sample Output 1

3

Cho lưới ô vuông rộng vô tận, tâm của lưới ô vuông có tọa độ (0, 0). Có ~n~ ngôi nhà được xây dựng trên lưới ô vuông. Trong 1 đơn vị thời gian, người ~A~ có thể di chuyển đến các ô liền kề của lưới (8 ô liền kề). Khoảng cách giữa 2 ngôi nhà là thời gian ngắn nhất di chuyển từ nhà này đến nhà kia. Trong lúc nhàn rỗi, bạn Lương tính toán hết tất cả khoảng cách giữa 2 ngôi nhà và sắp xếp chúng thành dãy không giảm. Hãy tìm số thứ ~k~ trong dãy.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~n, k~ ~(2 \leq n \leq 10^5, k \leq \frac{n (n - 1)}{2})~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa 2 số nguyên ~x, y~ là tọa độ của nhà thứ ~i~ ~(|x|, |y| \leq 10^9)~.

Output

• In ra số nguyên là kết quả bài toán.

Scoring

• Subtask 1: ~\ n \leq 2000~
• Subtask 2: ~\ y_i = 0~ với mọi ~i~
• Subtask 3: ~\ k = 1~
• Subtask 4: không có dữ kiện gì thêm

Sample Input 1

4 3
3 1
1 -1
0 5
-2 1

Sample Output 1

4

Reimu cần phong ấn một cuốn sách. Cô có ~n~ lá bùa, trên lá bùa thứ ~i~ có số nguyên dương ~a_i~. Để phong ấn cuốn sách cô cần chọn một số lá bùa trong số ~n~ lá bùa sao cho tích của chúng kết thúc bằng chữ số ~d~ và để đạt được hiệu quả cao thì tích phải là lớn nhất có thể. Bạn hãy giúp cô tìm ra những lá bùa cần sử dụng nhé!

Input

• Dòng đầu gồm 2 số nguyên dương ~n, d (1 \le n \le 100000, 0 \le d \le 9).~
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_i~.

Output

• Dòng đầu tiên là số tự nhiên ~k~ là số lượng lá bùa được chọn hoặc không có cách chọn in ra ~-1~.
• Nếu có cách chọn thì dòng tiếp theo số trên những lá bùa được chọn (có thể theo thứ tự ngẫu nhiên).

Sample Test

Input:

6 3
8 9 4 17 11 5

Output:

3
9 11 17 

Cho một dãy ~a~ gồm ~n~ phần tử phân biệt. Chúng ta được thực hiện thao tác sau vô số lần: di chuyển một phần tử ra khỏi dãy, sau đó chèn nó vào một vị trí bất kì trong dãy. Yêu cầu: Hãy tìm số lần thực hiện thao tác ít nhất để đưa dãy về dãy tăng dần.

Input

• Dòng đầu tiên gồm số nguyên ~n~ miêu tả số lượng phần tử.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output

• Gồm một dòng duy nhất là kết quả bài toán.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le a \le 10^9~

Sample Input 1

5
1 5 4 2 3 

Sample Output 1

2

Explanation 1

• Chèn số ~4~ vào sau số ~3~ thu được dãy : 1 5 2 3 4
• Chèn số ~5~ vào sau số ~4~ thu được dãy : 1 2 3 4 5
• Tổng cộng hết hai thao tác.