Cây nhiễm độc (Poisonous Plants)

Nguồn: HackerRank

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ cây xếp từ trái sang phải; cây $i$ có lượng thuốc trừ sâu $p_i$. Sau mỗi ngày, mọi cây có lượng thuốc lớn hơn cây còn sống ngay bên trái của nó sẽ chết đồng thời. Quá trình lặp lại trên dãy cây còn sống. Hãy tính số ngày cho đến khi không còn cây nào chết.

Input

Dòng đầu chứa $N$. Dòng thứ hai chứa $N$ số nguyên $p_1,p_2,\ldots,p_N$.

Output

In số ngày cần thiết cho đến khi không còn cây nào chết.

Subtask

• Subtask 1 (30 điểm): $N\le2000$; các điều kiện khác giữ nguyên.
• Subtask 2 (70 điểm): $1\le N\le10^5$, $0\le p_i\le10^9$.

Ví dụ

Input

7
6 5 8 4 7 10 9

Output

2

Giải thích

Ban đầu lượng thuốc của các cây là $[6,5,8,4,7,10,9]$.

Ngày $1$, mỗi cây được so với cây đang sống ngay bên trái theo trạng thái đầu ngày:

• $8>5$, nên cây có mức $8$ chết;
• $7>4$, nên cây có mức $7$ chết;
• $10>7$, nên cây có mức $10$ chết.

Sau ngày $1$, dãy còn lại là $[6,5,4,9]$.

Ngày $2$, cây có mức $9$ đứng ngay bên phải cây mức $4$ và $9>4$, nên cây này chết. Dãy còn lại là $[6,5,4]$.

Từ đây $6\ge5\ge4$, không còn cây nào có lượng thuốc lớn hơn cây ngay bên trái. Quá trình dừng sau $2$ ngày, nên output là 2.