F. KHONGTANG - Dãy con không tăng

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Trình chấm ngoài

Đề bài

Cho dãy số nguyên a_1,a_2,\ldots,a_n . Hãy tìm dãy con không tăng dài nhất gồm các phần tử liên tiếp của dãy đã cho (tức là tìm một đoạn các phần tử a_u≥a_(u+1)≥\ldots≥a_v gồm nhiều phần tử nhất).

Dữ liệu:

  • Dòng đầu chứa số nguyên dương n ;
  • Dòng sau chứa n số nguyên a_1,a_2,\ldots,a_n\ (|a_i|≤10^9) .

Kết quả:

  • Một dòng duy nhất ghi hai số nguyên dương là chỉ số đầu và chỉ số cuối của đoạn không tăng.

Ví dụ:

Dữ liệu:

6
3 2 3 1 1 2

Kết quả:

3 5

Giải thích:

  • Đoạn gồm 3 phần tử từ phần tử thứ 3 đến phần tử thứ 5 gồm các số 3,1,1 là đoạn không tăng dài nhất.

Chú ý cách chấm điểm:

  • Nếu đoạn bạn đưa ra không phải đoạn không giảm thì bạn sẽ không có điểm của test đó;
  • Nếu đoạn bạn đưa ra là đoạn không giảm thì số điểm bạn đạt được sẽ phụ thuộc vào tỉ lệ độ dài dãy con của bạn với đáp án của tác giả (ví dụ đáp án của tác giả có độ dài là 10 và độ dài dãy con của bạn là 8 thì bạn sẽ được 80\% số điểm của test đó).

Giới hạn:

  • Subtask \#1: 70\% số điểm của bài có n≤200 ;
  • Subtask \#2: 20\% số điểm khác có n≤5000 ;
  • Subtask \#3: 10\% số điểm còn lại có n≤10^5 .