You are given a sequence $A_1, A_2, \ldots, A_N$. Calculate the number of ways to remove a non-empty contiguous subsequence from it such that the resulting sequence is non-empty and strictly increasing.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of ways.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 10^5$
- $|A_i| \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (40 points): $N \le 1,000$
Subtask #2 (60 points): original constraints

-----Example Input-----
2
3
1 1 2
4
2 4 3 5

-----Example Output-----
4
7

Difficulty: interview

Starter code:

Solutions:
import bisect

def pre(a):
 for p in range(n-1):
  if(a[p]>=a[p+1]):
   return p
 return n-1 
 
def suf(a):
 for s in range(1,n):
  if(a[n-s]<=a[n-s-1]):
   return n-s
 return 0
 
 

t=int(input())
for _ in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 
 p=pre(a)
 s=suf(a)
 
 b=a[s:n]
 count=0
 for i in range(p+1):
  k=bisect.bisect(b,a[i])
  k+=s
  count+=n-k+1
  
 if(s==0):
  print((n*(n+1))//2-1)
 else:
  print(count+n-s)


for t in range(int(input())):
 n = int(input())
 a = list(map(int, input().split()))
 first_index = 0
 last_index = 0
 curr_index = 0
 indexes = [[0, 0]]
 for i in range(1,n):
  if a[i] > a[i-1]:
   last_index = i
  else:
   indexes[curr_index][1] = last_index
   curr_index += 1
   last_index += 1
   first_index = last_index
   indexes.append([first_index, last_index])
 indexes[curr_index][1] = last_index
 res = 0
 if len(indexes)>1:
  res = indexes[0][1] - indexes[0][0] + 1
  res += indexes[-1][1] - indexes[-1][0] + 1
  first_range_last_index = indexes[0][1]
  last_range_first_index = indexes[-1][0]
  n -= 1
  while first_range_last_index >= 0 and n>=last_range_first_index:
   if a[n] <= a[first_range_last_index]:
    res += len(a) - (n+1)
    first_range_last_index -= 1
   else:
    n -= 1
  if first_range_last_index>=0 :
   res += (first_range_last_index+1) * (len(a) - (n+1))
 else:
  res = (((n)*(n+1)) // 2)-1

 print(res)

t = int(input())
for _ in range(t):
 n = int(input())
 a = list(map(int, input().split()))
 e = n - 1
 for i in range(n - 2, -1, -1):
  if a[i + 1] > a[i]:
   e = i
  else:
   break
 cnt = 0
 for i in range(n):
  if i - 2 >= 0 and a[i - 2] >= a[i - 1]:
   break
  if e <= i:
   e = i + 1
  while e < n and i - 1 >= 0 and a[i - 1] >= a[e]:
   e += 1
  cnt += n - e + 1
 print(cnt - 1)



for _ in range(int(input())):
 n = int(input())
 
 seq = list(map(int, input().split()))
 
 if n == 1:
  print(0)
  continue
 
 pref, suff = 0, n-1
 
 for i in range(1, n):
  if seq[i] > seq[i-1]:
   pref = i
  else:
   break
 
 for i in range(n-2, -1, -1):
  if seq[i] < seq[i+1]:
   suff = i
  else:
   break
  
 l, r, ans = 0, suff, 0
 
 while r < n and l <= pref:
  if seq[l]<seq[r]:
   ans+=(n-r)
   l += 1
  else:
   r+=1
 
 if suff < pref:
  print((n*(n+1))//2-1)
  continue
   
 print(ans+(pref+1)+(n-suff))
   
  



for _ in range(int(input())):
 n = int(input())
 
 if n == 1:
  print(0)
  continue
 
 seq = list(map(int, input().split()))
 
 pref, suff = 0, n-1
 
 for i in range(1, n):
  if seq[i] > seq[i-1]:
   pref = i
  else:
   break
 
 for i in range(n-2, -1, -1):
  if seq[i] < seq[i+1]:
   suff = i
  else:
   break
  
 l, r, ans = 0, suff, 0
 
 while r < n and l <= pref:
  if seq[l]<seq[r]:
   ans+=(n-r)
   l += 1
  else:
   r+=1
 
 if suff < pref:
  print((n*(n+1))//2-1)
  continue
   
 print(ans+(pref+1)+(n-suff))
   
  



for _ in range(int(input())):
 n = int(input())
 
 seq = list(map(int, input().split()))
 
 pref, suff = 0, n-1
 
 for i in range(1, n):
  if seq[i] > seq[i-1]:
   pref = i
  else:
   break
 
 for i in range(n-2, -1, -1):
  if seq[i] < seq[i+1]:
   suff = i
  else:
   break
  
 l, r, ans = 0, suff, 0
 
 while r < n and l <= pref:
  if seq[l]<seq[r]:
   ans+=(n-r)
   l += 1
  else:
   r+=1
 
 if suff < pref:
  print((n*(n-1))//2+n-1)
  continue
   
 print(ans+(pref+1)+(n-suff))
   
  


t = int(input())
for _ in range(t):
 n = int(input())
 data = list(map(int,input().strip().split()))
 
 prefix = [False]*n
 suffix = [False]*n
 
 prefix[0] = True
 for i in range(1,n):
  if data[i]>data[i-1]:
   prefix[i] = True
  else:
   break
 
 suffix[n-1] = True
 for i in range(n-2,-1,-1):
  if data[i]<data[i+1]:
   suffix[i] = True
  else:
   break
   
 
 ans = 0
 if prefix.count(True) == n:
  ans = (n*(n-1))/2 + (n-1)
 else:
  for i in range(n):
   if prefix[i]:
    low =i
    high =n
    while(high-low>1):
     mid = (low+high)//2
     if suffix[mid] and data[i]<data[mid]:
      high = mid
     else:
      low = mid
    
    ans += n-high
   else:
    break
    
  ans += suffix.count(True)
  ans += prefix.count(True)
  
 print(int(ans))


t = int(input())
for _ in range(t):
 n = int(input())
 data = list(map(int,input().strip().split()))
 
 prefix = [False]*n
 suffix = [False]*n
 
 prefix[0] = True
 for i in range(1,n):
  if data[i]>data[i-1]:
   prefix[i] = True
  else:
   break
 
 suffix[n-1] = True
 for i in range(n-2,-1,-1):
  if data[i]<data[i+1]:
   suffix[i] = True
  else:
   break
   
 
 ans = 0
 if prefix.count(True) == n:
  ans = (n*(n-1))/2 + (n-1)
 else:
  for i in range(n):
   if prefix[i]:
    val = 0
    for j in range(n):
     if suffix[j] and data[j]>data[i]:
      val = j
      break
    
    if val!=0:
     ans += n-val
   else:
    break
    
  ans += suffix.count(True)
  ans += prefix.count(True)
  
 print(int(ans))


# cook your dish here
def bin(arr,l,r,val,n):
 ans=n
 while(l<=r):
  mid=(l+r)//2
  if(arr[mid]<=val):
   l=mid+1
  else:
   ans=mid
   r=mid-1
 return ans


t=int(input())
while(t):
 n=int(input())
 arr=list(map(int,input().strip().split(' ')))
 pre=[]
 suff=[0]*n
 pre.append(1)
 for i in range(1,n):
  if(arr[i]>arr[i-1] and pre[i-1]==1):
   pre.append(1)
  else:
   pre.append(0)
 flag=0
 temp=0
 for i in range(n-1,-1,-1):
  if(i==n-1):
   suff[i]=1
  elif(arr[i]<arr[i+1] and suff[i+1]==1):
   suff[i]=1
  else:
   if(flag==0):
    temp=i+1
    #print(temp)
    suff[i]=0
    flag=1
   else:
    suff[i]=0
    #flah=1
 
 #print(pre,end=' ')
 #print()
 #print(suff,end='')
 #print(temp)
 count=0
 y=n
 for i in range(n):
  y=n
  if(pre[i]==1):
   count+=1
   if(temp>i+1):
    y=bin(arr,temp,n-1,arr[i],n)
   elif(i+2<n):
    y=bin(arr,i+2,n-1,arr[i],n)
   #print(y)
   count+=(n-y)
     #print(n-j)
     #break
 count+=(n-temp)
 if(pre[temp]==1):
  count-=2
 print(count)
 t-=1

# cook your dish here
t=int(input())
while(t):
 n=int(input())
 arr=list(map(int,input().strip().split(' ')))
 pre=[]
 suff=[0]*n
 pre.append(1)
 for i in range(1,n):
  if(arr[i]>arr[i-1] and pre[i-1]==1):
   pre.append(1)
  else:
   pre.append(0)
 flag=0
 temp=0
 for i in range(n-1,-1,-1):
  if(i==n-1):
   suff[i]=1
  elif(arr[i]<arr[i+1] and suff[i+1]==1):
   suff[i]=1
  else:
   if(flag==0):
    temp=i+1
    #print(temp)
    suff[i]=0
    flag=1
   else:
    suff[i]=0
    #flah=1
 
 #print(pre,end=' ')
 #print()
 #print(suff,end='')
 #print(temp)
 count=0
 for i in range(n):
  if(pre[i]==1):
   count+=1
   for j in range(temp,n):
    if(arr[j]>arr[i] and j>i+1):
     count+=(n-j)
     #print(n-j)
     break
 count+=(n-temp)
 if(pre[temp]==1):
  count-=2
 print(count)
 t-=1

T = int(input())

while T>0:
 n = int(input())
 a = list(map(int, input().split()))
 prefix = [True for k in range(n)]
 suffix = [True for k in range(n)]
 
 for i in range(1, n):
  prefix[i] = prefix[i-1] and (a[i] > a[i-1])
 for i in range(n-2, -1, -1):
  suffix[i] = suffix[i+1] and (a[i] < a[i+1])
 
 lo = 0
 hi = n - 1
 while lo < hi:
  mid = (lo + hi)//2
  if suffix[mid]:
   hi = mid
  else:
   lo = mid + 1 
 ans = n - lo 
 #print(ans)
 for i in range(n-1):
  if prefix[i]:
   lo = i + 1
   hi = n - 1
   while lo < hi:
    mid = (lo + hi)//2
    if suffix[mid] and a[mid] > a[i]:
     hi = mid
    else:
     lo = mid + 1
   ans += (n - lo + 1)
   if lo == i + 1 or (lo == n-1 and a[lo] < a[i]):
    ans -=1
   #print(ans)
  else:
   break
 if prefix[-1]:
  ans -= 1
 print(ans)
 T-=1
 
  


t = int(input())
for i in range(t):
 n = int(input())
 a = list(map(int,input().split(' ')))
 start=-1
 for i in range(len(a)-1):
  if a[i] >= a[i+1]:
   start=i
   break
 end=-1
 for i in range(len(a)-1,0,-1):
  if a[i] <= a[i-1]:
   end=i
   break
 # print(start,end)
 if start==-1:
  ans=((n*(n+1))//2) - 1
  print(ans)
 else:
  j=len(a)-1
  k=0
  c=1
  for i in range(start,-1,-1):
   while a[j]>a[i] and j>=end:
    j-=1
    c+=1
   k+=c
   # print(k)
  k+=len(a)-end
  print(k)
  # print(k+2)


# cook your dish here
import bisect

for t in range(int(input())):
 n=int(input())
 arr=[int(a) for a in input().split()]
 prifix=list()
 prefix=[False for _ in range(n)]
 for i in range(0,n):
  if(i==0):prefix[i]=True
  else:
   if arr[i]>arr[i-1]:
    prefix[i]=True
   else:break
 sufix=list()
 sufix=[False for _ in range(n)]
 for i in range(n-1,-1,-1):
  if(i==n-1):sufix[i]=True
  else:
   if arr[i]<arr[i+1]:
    sufix[i]=True
   else:break
 left=0
 right=0 
 for i in range(n):
  if prefix[i]==True:
   left=i
 for i in range(n-1,-1,-1):
  if sufix[i]==True:
   right=i
 ans=0
 if right==0 and left==n-1:
  ans=(n*(n+1)//2)-1
  
 else:
  i=0
  while(prefix[i]==True):
   if arr[i]>arr[n-1]:ans+=1
   else:
    k=bisect.bisect_left(arr, arr[i],right,n-1)
    ans+=n-k+1
    if(arr[k]==arr[i]):ans-=1
   i+=1
  ans+=n-right
 print(ans)

T = int(input())

def bSearch(A,suff, k, i, j):
 # print('-?', k, i, j)
 if i>=len(A):
  return
 if i == j:
  if suff[i]==False or A[j]<=A[k]:
   return
  return i
 mid = (i + j)//2
 if mid <= k:
  return bSearch(A,suff, k, mid+1, j)
 else:
  if A[mid] <= A[k] or suff[mid]==False:
   return bSearch(A,suff, k, mid+1, j)
  else:
   return bSearch(A,suff, k, i, mid)


for _ in range(T):
 N = int(input())
 A = list(map(int, input().split()))
 pref = [False for _ in range(N)]
 suff = [False for _ in range(N)]
 pref[0] = True
 suff[-1] = True
 for i in range(1, N):
  if A[i] > A[i-1]:
   pref[i] = True
  else:
   break
 for i in reversed(range(N-1)):
  if A[i] < A[i+1]:
   suff[i] = True
  else:
   break

 count = 0
 for i in range(N):
  if pref[i] == True:

   j = bSearch(A,suff, i, i+1, N-1)
   if j == None:
    # print(i, N)
    if i<N-1:
     count += 1
    # break
   elif j == i+1:
    count += N-j
    # print(i, j, N-j)
   else:
    count += N - j + 1
    # print(i, j, N-j+1)
   
 for i in range(1, N):
  if suff[i] == True:
   count += 1
 
 print(count) 

def bin_search1(arr, x):
 s = 0
 e = len(arr)-1
 while s <= e:
  m = (s+e)//2
  if arr[m] > x:
   e = m-1
  else:
   s = m+1
  # print(s, e)
 # print(s)
 return s


def bin_search2(arr, x):
 s = 0
 e = len(arr)-1
 while s <= e:
  m = (s+e)//2
  if arr[m] >= x:
   e = m-1
  else:
   s = m+1
  # print(s, e)
 # print(s)
 return s





t = int(input())
for i in range(t):
 n = int(input())
 arr = [int(j) for j in input().split()]
 var = 0
 flag = 0
 for i in range(n-1):
  if arr[i+1] <= arr[i]:
   var = 1
   ind1 = i
   break

 if var == 0:
  print((n*(n+1))//2 -1)
  continue


 for i in range(n-1, 0, -1):
  if arr[i-1] >= arr[i]:
   ind2 = i
   break

 # print(ind1, ind2)
 arr1 = arr[:ind1+1]
 arr2 = arr[ind2:]

 # print(arr1, arr2)

 count = len(arr1) + len(arr2)
 for i in range(len(arr1)):
  x = bin_search1(arr2, arr1[i])
  # print(x)
  count += len(arr2)+1-x

 # print(count)
 for i in range(len(arr2)):
  x = bin_search1(arr1, arr2[i])
  # print(x)
  count += x+1

 print(count//2)






def bin_search1(arr, x):
 s = 0
 e = len(arr)-1
 while s <= e:
  m = (s+e)//2
  if arr[m] > x:
   e = m-1
  else:
   s = m+1
  # print(s, e)
 # print(s)
 return s


def bin_search2(arr, x):
 s = 0
 e = len(arr)-1
 while s <= e:
  m = (s+e)//2
  if arr[m] >= x:
   e = m-1
  else:
   s = m+1
  # print(s, e)
 # print(s)
 return s





t = int(input())
for i in range(t):
 n = int(input())
 arr = [int(j) for j in input().split()]
 var = 0
 flag = 0
 for i in range(n-1):
  if arr[i+1] <= arr[i]:
   var = 1
   ind1 = i
   break

 if var == 0:
  print((n*(n+1))//2 -1)
  continue


 for i in range(n-1, 0, -1):
  if arr[i-1] >= arr[i]:
   ind2 = i
   break

 # print(ind1, ind2)
 arr1 = arr[:ind1+1]
 arr2 = arr[ind2:]

 # print(arr1, arr2)

 count = len(arr1) + len(arr2)
 for i in range(len(arr1)):
  x = bin_search1(arr2, arr1[i])
  # print(x)
  count += len(arr2)+1-x

 # print(count)
 for i in range(len(arr2)):
  x = bin_search2(arr1, arr2[i])
  # print(x)
  count += x+1

 print(count//2)






from sys import stdin
input=stdin.readline
for i in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 if all((a[i] < a[i + 1] for i in range(n - 1))):
   print(n * (n + 1) // 2 - 1)
   continue
 for i in range(1, n):
  if a[i - 1] >= a[i]:
   arr1 = a[:i]
   break
 for j in range(n - 1, 0, -1):
  if a[j - 1] >= a[j]:
   arr2 = a[j:]
   break

 ans=len(arr1)+len(arr2)
 le=len(arr2)
 x=0
 for i in arr1: 
  while x<len(arr2) and arr2[x]<=i:
   x+=1
   le-=1
  if x==len(arr2):
   break
  ans+=le
 print(ans)

for _ in range(int(input())):
 n = int(input())
 arr = list(map(int,input().split()))
 front = [0 for i in range(n)]
 back = [n-1 for i in range(n)]
 for i in range(1,n):
  if front[i-1]==i-1 and arr[i]>arr[i-1]:
   front[i] = i
  else:
   front[i] = front[i-1]
 for i in range(n-2,-1,-1):
  if back[i+1]==i+1 and arr[i]<arr[i+1]:
   back[i] = i
  else:
   back[i] = back[i+1]
 ans = n-back[0]
 for i in range(1,n):
  if front[i-1]==i-1:
   ans+=1
   key = arr[i-1]
   low = back[i]
   high = n-1
   if arr[high]>key:
    flag = False
    while low<high:
     mid = (low+high)//2
     if arr[mid]>key:
      high = mid
     else:
      low = mid
     if low+1==high:
      if flag:
       high-=1
      flag = True
    mid = (low+high)//2
    if arr[mid]<=key:
     mid+=1
    ans += (n-mid)
 if back[0]==0:
  ans-=n
 print(ans)


for _ in range(int(input())):
 n = int(input())
 arr = list(map(int,input().split()))
 front = [0 for i in range(n)]
 back = [n-1 for i in range(n)]
 for i in range(1,n):
  if front[i-1]==i-1 and arr[i]>arr[i-1]:
   front[i] = i
  else:
   front[i] = front[i-1]
 for i in range(n-2,-1,-1):
  if back[i+1]==i+1 and arr[i]<arr[i+1]:
   back[i] = i
  else:
   back[i] = back[i+1]
 if(back[0]==0):
  print(2*n-2+(n-2)*(n-1)//2)
 else:
  ans = n-back[0]
  for i in range(1,n):
   if front[i-1]==i-1:
    ans+=1
    key = arr[i-1]
    low = back[i]
    high = n-1
    if arr[high]>key:
     flag = False
     while low<high:
      mid = (low+high)//2
      if arr[mid]>key:
       high = mid
      else:
       low = mid
      if low+1==high:
       if flag:
        high-=1
       flag = True
     mid = (low+high)//2
     if arr[mid]<=key:
      mid+=1
     ans += (n-mid)
    
  print(ans)