Xếp Hàng Kỹ Thuật Hồ Chí Minh

Mô tả

Công viên chủ đề mang tên Kỹ Thuật Hồ Chí Minh tổ chức ngày mở cửa miễn phí cho các kỹ sư. Tại cửa soát vé chỉ có đúng một quầy, và mọi người phải xếp hàng theo thứ tự đến.

Tuy nhiên, các kỹ sư có một thói quen đặc biệt: không ai muốn đứng đằng sau người đến muộn hơn mình. Nếu một người đang đứng trong hàng mà phía sau lưng có ai đó đến muộn hơn, người đó sẽ bực mình và lập tức rời khỏi hàng. Những người phía trước thì không bị ảnh hưởng.

Mỗi lượt soát vé mất đúng 1 phút cho một người. Hãy tính tổng thời gian (số phút) cần thiết để phục vụ hết tất cả những người còn ở lại trong hàng cuối cùng.

Biết rằng thời gian đến đã được sắp xếp theo thứ tự tăng dần.

Đầu vào

• Một mảng arr gồm n số nguyên dương, trong đó arr[i] là thời gian đến của người thứ i (tính bằng phút, tính từ thời điểm mở cửa). Các giá trị đã cho theo thứ tự tăng dần.

Đầu ra

• Trả về một số nguyên: tổng số phút cần thiết để phục vụ tất cả những người còn lại trong hàng cuối cùng.

Ràng buộc

• 1 <= n <= 10^5
• 1 <= arr[i] <= 10^9
• arr[i] <= arr[i+1] với mọi i.

Ví dụ

Ví dụ 1:

• Đầu vào: [1, 2, 3]
• Đầu ra: 3
• Giải thích: Người đến lúc 1 đứng đầu, người đến lúc 2 đứng sau (2 > 1, hợp lệ). Người đến lúc 3 đứng cuối (3 > 2, hợp lệ). Cả ba người đều ở lại và được phục vụ: 1 + 1 + 1 = 3 phút.

Ví dụ 2:

• Đầu vào: [4, 4, 4]
• Đầu ra: 3
• Giải thích: Người thứ hai (4) không muộn hơn người thứ nhất (4). Người thứ ba (4) không muộn hơn người thứ hai (4). Vì không ai phía sau đến muộn hơn nên tất cả đều ở lại. Tổng thời gian: 1 + 1 + 1 = 3 phút.