TBIKE - Đạp xe

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Vào những buổi chiều cuối tuần, Tuệ thường đạp xe chở bạn gái đi chơi. Tuy nhiên, việc dành quá nhiều thời gian với máy tính đã làm suy giảm thể trạng của cậu ta. Do vậy, bạn gái của Tuệ quyết định bắt cậu ta phải tập đạp xe vòng quanh hồ Hoàn Kiếm như 1 biện pháp để tăng cường sức khỏe.

Vào những ngày Tuệ tập luyện, bạn gái của Tuệ sẽ tới theo dõi cậu ta một lần. Trong suốt quãng thời gian theo dõi, cô ta sẽ ghi lại thời điểm Tuệ bắt đầu 1 vòng đạp mới quanh hồ (có thể không đủ tất cả các vòng của ngày hôm đó nhưng luôn đảm bảo số liệu được ghi nhận là của những vòng đạp liên tiếp nhau). Cách Tuệ đạp xe cũng khá thú vị, mặc dù vận tốc mỗi ngày là khác nhau (có thể do tác động của thời tiết, sức khỏe, tâm trạng...) nhưng trong 1 ngày, cậu ta luôn đạp với 1 vận tốc không đổi.

Đến 1 ngày, Tuệ muốn xem lại quá trình tập luyện của mình, nhưng cậu bất ngờ phát hiện ra các số liệu được ghi lại không theo 1 thứ tự nào cả. Hỏi ra mới biết, đây là thử thách của bạn gái dành cho cậu ta. Tuệ phải xác định được ít nhất mình đã tập luyện được bao nhiêu ngày với 1 gợi ý từ bạn gái rằng số liệu của các vòng đạp trong cùng 1 ngày luôn luôn là 1 dãy liên tiếp trong toàn bộ dãy số liệu.

Input

Dòng 1: Số N là số lượng thời điểm được ghi chép lại.
Dòng 2: N số là các thời điểm.

Output

Số ngày ít nhất mà Tuệ đã tập luyện.

Constraints

N ≤ 2000
Các số trong input là số nguyên dương không vượt quá 10 9

Example 

Input:
4
20 8 12 16

Output:
1

Input: 
6
1 3 2 3 7 5

Output:
2

Giải thích: thời điểm của ngày 1 là 1,3,2 ; thời điểm của ngày 2 là 3,7,5.

  • Người up: hphong
  • Nguồn bài: Problem setter : Nguyễn Tấn Sỹ Nguyên