Sau khi xem xong MV "Ice Cream" của Blackpink, bin9638 và algorit liền đặt ngay vé máy bay sang Hàn Quốc để có thể ăn kem tại quán và nói chuyện với các idol của mình. Lúc bin9638 và algorit tới quán kem "Blackpink" thì đúng lúc quán kem này đang có chương trình phát kem cho các em nhỏ. Cụ thể, có \(n\) đứa trẻ lần lượt có độ tuổi là \(A_1 , A_2 , ... , A_n\) đang đứng trước quán chờ nhận kem, đứa trẻ thứ \(i\) có độ tuổi là \(A_i\) . Chương trình phát kem của Blackpink cũng rất đặc biệt, mỗi đứa trẻ phải có ít nhất \(1\) que kem , khi có \(2\) đứa trẻ đứng gần nhau , đứa trẻ lớn hơn sẽ được phát nhiều kem hơn, nếu \(2\) đứa trẻ cùng tuổi đứng cạnh nhau thì phát tùy ý. Tuy nhiên vì còn phải đi phát kem ở nhiều nơi nữa nên Blackpink muốn số kem được phát là tối thiểu.

Lisa, quản lí của quán kem này biết bin9638 và algorit là những người rất thông minh nên muốn nhờ họ tính giúp số kem tối thiểu cần phát. Nếu tính được thì bin9638 và algorit sẽ được tặng \(2\) que kem, hơn nữa họ còn sẽ được chụp ảnh chung và có được chữ kí của Blackpink nữa đấy. Hãy giúp họ nhé !

Yêu cầu:

• Hãy tìm số lượng kem tối thiểu đề chia cho \(n\) đứa trẻ.

Input:

• Dòng đầu tiên gồm \(1\) số nguyên dương \(n\) . \((n \le 10^6)\)
• Dòng thứ \(2\) là dãy số \(A_1 , A_2 , ... , A_n\) là độ tuổi của nhứng đứa trẻ . \((A_i \le 10^9)\)

Output:

• Dòng đầu tiên gồm một số nguyên dương duy nhất là số lượng kem tối thiểu.
• Dòng thứ \(2\) là dãy \(C_i\) tương ứng với số kem phát cho đứa trẻ thứ \(i\).

Scoring:

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3\)
• Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.

Example

5
1 2 1000000000 2 1 

9
1 2 3 2 1 

3
1 2 2 

4
1 2 1