Cho ~N~ bình chứa nước lần lượt có thể tích là các số ~a_1.. a_N~. Khi xếp các bình theo một dãy thì sẽ tạo thành 1 khối. Nếu xếp lần lượt các bình chứa nước theo trình tự đó thì thể tích cả khối là ~a_1 + a_2 + ... + a_N + max(0, a_2 - a_1) + max(0, a_3 - a_2) + ... + max(0,a_N - a_{N - 1}~. Nhiệm vụ của bạn là tìm cách xếp sao cho tổng thể tích chứa của cả khối là lớn nhất có thể.

Dữ liệu:

• Dòng đầu ghi số nguyên dương ~N~ (~0 < n ≤ 10^5~).
• ~N~ dòng sau mỗi dòng ghi một số ~a_i~ ( ~1 ≤ i ≤ N và 1 ≤ a_i ≤ 10000~).

Kết quả:

• Ghi trên một dòng kết quả là thể tích lớn nhất tìm được.

Ví dụ

Input

4
5 4 1 7

Output

24

Nam rất thích nghiên cứu về toán. Bài toán hiện tại mà cậu ấy đang nghiên cứu là dãy Fibonacci với quy luật như sau:

• ~𝑓_0 = 0; 𝑓_1 = 𝑥~
• ~𝑓_n = 𝑓_{n-1} + 𝑓_{n-2}~

Nam rất thích thú khi đã tính được tới số Fibonacci thứ 𝑛. Sau đó cậu quyết định đi ngủ. Trong lúc ngủ, không biết rằng chị Hằng đã chui từ đâu ra và phá nát mất 2 số ~𝑓_0~ và ~𝑓_1~ của Nam. Nam ngồi khóc một mình trong 4 bức tường vì cậu ấy không thể tìm ra được số 𝑥 của mình. Điều mà Nam vẫn còn nhớ trong đầu đó là số ~𝑓_0~ đầu tiên chắc chắn là số 0 và số 𝑛 và giá trị ~𝑓_n~. Nhưng Nam đã quên số 𝑥 rồi.

Yêu cầu: Hãy giúp Nam tìm lại số 𝑥 của mình nhé!

Input:

• Dòng 1: Gồm hai số là lượt là 𝑛 và ~𝑓_n (2 \le 𝑛 \le 100)~.

Output:

• Dòng 1: Gồm một số nguyên duy nhất là số 𝑥

Example:

Input:

6 8

Output:

1

Viết chương trình nhập vào số tự nhiên ~n~, tính tổng các ước thực sự của ~n~ (ước thực sự là ước nhỏ hơn ~n~).

Input

Nhập từ bàn phím một số tự nhiên ~n~ (~1 < n ≤ 10^{10}~).

Output

• Xuất ra màn hình tổng các ước thật sự của ~n~.

Example

Input

6

Output

6

Note

• Các ước thật sự của 6 là 1, 2, 3 nên tổng ước thật sự của 6 bằng 6.

Mật khẩu được xem là mạnh khi thỏa mãn các điều kiện sau đây:

• Có độ dài ít nhất là 6.
• Có ít nhất 1 ký tự tiếng Anh in hoa
• Có ít nhất một ký tiếng Anh tự in thường
• Có ít nhất 1 chữ số
• Có ít nhất một ký tự đặc biệt thuộc ! @#$%^& ∗ () –

Yêu cầu: Cho số nguyên dương 𝑛, xâu 𝑠 có 𝑛 ký tự. Hãy cho biết cần thêm vào xâu 𝑠 ít nhất bao nhiêu ký tự để 𝑠 trở thành một mật khẩu mạnh?

Input:

• Dòng 1: Ghi số nguyên dương 𝑛
• Dòng 2: Ghi 𝑛 ký tự của xâu 𝑠

Output:

• In ra một số nguyên duy nhất là đáp án của bài toán.

Example:

Input:

3
Ab1

Output:

3

Constraints:

~1 \le 𝑛 \le 10^4~;