There are two ways to write error-free programs; only the third one works!

Cho hai số nguyên ~X~ và ~N~.

Hãy tìm số nguyên dương ~Y~ để ~X \times Y = N~

Input

• Dòng đầu tiên chứa số nguyên ~X~ ~(|X| \le 10^9, X \neq 0)~;
• Dòng thứ hai chứa số nguyên ~N~ ~(|N| \le 10^9)~.

Output

Nếu có số ~Y~ thoả mãn yêu cầu đề bài thì in ra ~Y~, ngược lại, in ra ~NA~.

Examples

Input

3
6

Output

2

Input

-3
6

Output

NA

Sau khi bán hết sách, TDZ chuyển sang mở một quán cà phê.

Qua thăm dò, TDZ đã biết trước ngày khai trương sẽ có ~n~ khách, khách thứ ~i~ sẽ vào thời điểm ~h_i~. Để phục vụ lượng khách đến dồn dập, quán cà phê có thuê thêm một số nhân viên ưu tú. Mỗi nhân viên có thể hoạt động không ngừng nghỉ, mỗi lần chỉ phục vụ một khách trong đúng ~1~ đơn vị thời gian. Nhưng nếu một vị khách tới mà không nhận được sự phục vụ ngay thì sẽ lập tức bỏ đi.

Ví dụ, một vị khách đến ở thời điểm ~5~, thì nhân viên sẽ phục vụ xong cho vị khách đó ở thời điểm ~6~ và tiếp tục phục vụ luôn khách tiếp theo (nếu có).

Hãy giúp TDZ tìm ra số lượng nhân viên cần thuê ít nhất mà vẫn đảm bảo tất cả các khách đều được phục vụ.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~h_1, h_2, h_3, \ldots, h_n~ tương ứng với thời điểm khách đến (~h_i \leq 10^5~).

Output

In ra số lượng nhân viên ít nhất cần thuê.

Sample Test

Input:

4
1 10 45 10

Output:

2

Đây là phiên bản khó hơn của bài PA120. Điểm khác biệt duy nhất giữa hai bài là số ~k~ và giới hạn các số.

Sau khi bán hết sách, TDZ chuyển sang mở một quán cà phê.

Qua thăm dò, TDZ đã biết trước ngày khai trương sẽ có ~n~ khách, khách thứ ~i~ sẽ vào thời điểm ~h_i~. Để phục vụ lượng khách đến dồn dập, quán cà phê có thuê thêm một số nhân viên ưu tú. Mỗi nhân viên có thể hoạt động không ngừng nghỉ, mỗi lần chỉ phục vụ một khách trong đúng ~k~ đơn vị thời gian. Nhưng nếu một vị khách tới mà không nhận được sự phục vụ ngay thì sẽ lập tức bỏ đi.

Cụ thể, một vị khách đến ở thời điểm ~x~ nào đó, thì nhân viên sẽ phục vụ xong cho vị khách đó ở thời điểm ~x + k~. Khách đó sẽ rời quán và nhân viên tiếp tục phục vụ luôn khách tiếp theo (nếu có).

Hãy giúp TDZ tìm ra số lượng nhân viên cần thuê ít nhất mà vẫn đảm bảo tất cả các khách đều được phục vụ.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~, ~k~ (~n \leq 10^6, k \leq 10^9~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~h_1, h_2, h_3, \ldots, h_n~ tương ứng với thời điểm khách đến (~h_i \leq 10^9~).

Output

In ra số lượng nhân viên ít nhất cần thuê.

Subtasks

• Subtask ~1~ (~25\%~): ~n \leq 10^3~.
• Subtask ~2~ (~37.5\%~): ~n \leq 10^6, h_i \leq 10^6~.
• Subtask ~3~ (~37.5\%~): Không có điều kiện gì thêm.

Sample Test

Input:

5 2
1 2 5 3 5

Output:

2

Note: Thuê hai nhân viên:

• Nhân viên thứ nhất sẽ phục vụ khách thứ nhất, rồi đến khách thứ tư và cuối cùng phục vụ khách thứ ba.
• Nhân viên thứ hai phục vụ khách thứ hai rồi đến khách thứ năm.

Cho dãy số nguyên ~a~ gồm ~n~ phần tử. Hãy tính tổng của ~|a_i-a_j|~ với mọi cặp ~(i,j)~ thỏa mãn ~1 \le i < j \le n~.

Input

• Dòng đầu gồm ~1~ số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng sau gồm ~n~ số nguyên miêu tả dãy ~a~ ~(|a_i| \le 10^6)~

Output

• In ra kết quả tìm được.

Sample Test

Input

3
5 1 2

Output

8

Cho số nguyên dương ~n~. Hãy đếm số cặp số nguyên dương ~(x, y)~ thoả mãn:

• ~1\le x, y \le n~.
• Chữ số đầu tiên của ~x~ bằng chữ số cuối cùng của ~y~.
• Chữ số đầu tiên của ~y~ bằng chữ số cuối cùng của ~x~.

Input

Một dòng duy nhất chứa số nguyên dương ~n~.

Output

Một số nguyên là số cặp ~(x, y)~ thoả mãn.

Examples

Input

11

Output

12

Giải thích

Các cặp số ~(x,y)~ thoả mãn: ~(1,1), (2,2), (3,3),(4,4), (5,5),(6,6),(7,7),(8,8),(9,9),(11,1),(1,11),(11,11)~.

Scoring

• Subtask ~1 \ (50\%)~: ~n \le 1000~.
• Subtask ~2 \ (50\%)~: ~n \le 10^6~.