40006. Practice 6: Peipei and Frenchfries II

I'm a slow walker, but I never walk backwards.

前情提要

由於裴裴所引領的風潮,「買到的大薯份量一定要比上一次買到的還多」已經變成大家吃麥當勞大薯的習慣了(跟裴裴不一樣的是,連跟上一次一樣多也不行)!

這個現象讓麥當勞的高層非常煩惱,因為再這樣子下去,不用過多久就不會有人要買薯條了。因此,麥當勞的高層決定開會把這個現象的原因找出來。然而,因為開會做決策很花時間,因此為了臨時應急,麥當勞需要好好規劃在做出決策前這段期間每天的大薯的份量要給多少。

為了方便規劃大薯份量,他們擬定了幾個接下來$N$天的薯條份量的計畫,並且他們需要知道: 對於每種計畫,假如每個來買薯條的客人都要求買到的大薯份量一定要比上一次買到的還多,「至少」要幾個不同的客人才能讓每天的大薯都賣出去?

舉例來說,如果他們打算接下來7天的薯條份量分別是4,2,6,5,1,8,3,則最少只需要三個客人就可以買完這些大薯:第一個人在第1,3天買,第二個人在第2,4,6天買,第三個人在第5,7天買。

因為麥當勞做的計畫實在是太多了,你的任務就是寫一個程式算出以上問題的答案。

Input/Output

輸入的第一行有一個正整數$T$,代表計畫的數量。 接下來每兩行代表一組計畫。第一行有一個正整數$N$,代表計畫的總天數;第二行有$N$個正整數$a_i$,代表每天的大薯份量。

請對每筆測資輸出一行,代表最少需要幾個客人才能買完這些大薯。

Subtasks/Constraints

所有測資皆符合: $T\leq 10; N\leq 10^ 6; a_i \leq 10^ 9$

  1. $N\leq 2$ (5 pts)
  2. $a_i \leq 2$ (15 pts)
  3. $N\leq 5000, a_i \leq 10$ (10 pts)
  4. $N\leq 500$ (10 pts)
  5. $N\leq 5000$ (10 pts)
  6. 保證答案不超過20 (10 pts)
  7. 無額外限制 (40 pts)

Sample Input

2
7
4 2 6 5 1 8 3
5
1 1 1 1 1

Sample Output

3
5

Discussion