Câu chuyện về khu vườn hoa của Furina - Thủy thần của Fortaine,một Thủy Thần đầy khoa trương và kiêu ngạo

Furina, một người yêu hoa say đắm, vừa mới tạo ra một luống hoa tuyệt đẹp với $n$ bông hoa được trồng thẳng hàng. Mỗi bông hoa lại có một vẻ đẹp và chiều cao riêng biệt. Chúng ta có thể gọi chiều cao ban đầu của bông hoa thứ $i$ trong hàng là hi​.

Khu vườn của Furina nằm ở một nơi đặc biệt, nơi mà cứ mỗi giây lại có một cơn gió mạnh mẽ thổi ngang qua, từ bên trái sang bên phải của luống hoa. Cơn gió này tác động đến chiều cao của những bông hoa theo một quy luật khá thú vị:

Trong mỗi giây gió thổi, chúng ta lần lượt xem xét từng bông hoa trong hàng, bắt đầu từ bông hoa đầu tiên cho đến bông hoa cuối cùng. Với mỗi bông hoa thứ $i$, sẽ xảy ra một trong hai trường hợp sau:

• Nếu bông hoa này là bông hoa cuối cùng trong hàng (tức là $i$ bằng với số lượng bông hoa $n$) hoặc nếu chiều cao hiện tại của bông hoa này lớn hơn chiều cao của bông hoa ngay phía sau nó, thì chiều cao của bông hoa này sẽ giảm đi đúng 1 đơn vị. Tuy nhiên, chiều cao của bông hoa không bao giờ có thể trở thành số âm, vì vậy chiều cao mới sẽ là giá trị lớn nhất giữa 0 và (chiều cao hiện tại trừ đi 1).
• Trong trường hợp ngược lại (bông hoa không phải là bông cuối cùng và chiều cao của nó không lớn hơn bông hoa đứng ngay sau nó), thì cơn gió trong giây này sẽ không làm thay đổi chiều cao của bông hoa đó.

Furina rất tò mò muốn biết phải mất bao nhiêu giây thì tất cả những bông hoa mà cô ấy đã trồng trong luống sẽ đồng loạt có chiều cao bằng 0 lần đầu tiên. Bạn hãy giúp Furina tìm ra con số thời gian kỳ diệu này nhé!

Dữ liệu đầu vào:

• Đầu tiên, bạn sẽ nhận được một số nguyên $t$ (với 1≤t≤1e5), đây là số lượng các khu vườn hoa khác nhau mà Furina đã trồng và bạn cần phải tính toán cho mỗi khu vườn.
• Với mỗi khu vườn, bạn sẽ nhận được hai dòng thông tin:
  • Dòng đầu tiên chứa một số nguyên $n$ (với 1≤n≤1e5), cho biết số lượng bông hoa trong luống.
  • Dòng thứ hai chứa $n$ số nguyên h1​,h2​,…,hn​ (với 1≤hi​≤1e9), đây là chiều cao ban đầu của từng bông hoa trong luống, theo thứ tự từ trái sang phải.
• Có một điều cần lưu ý là tổng số lượng bông hoa $n$ trong tất cả các khu vườn mà bạn cần tính toán sẽ không vượt quá 1e5.

  Yêu cầu:

  Đối với mỗi trường hợp kiểm tra, hãy xuất ra một số nguyên — số giây sẽ trôi qua trước khi hi=0 với mọi $\le i\le n$.