class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}



// 148. 排序链表
function sortList(head: ListNode | null): ListNode | null {
  //合并两个子链表
  function merge(h1:ListNode|null,h2:ListNode|null):ListNode|null{
      let p1 = h1
      let p2 = h2
      let vHead = new ListNode(-1)
      let p = vHead
      while(p1!=null&&p2!=null){
          if(p1.val<p2.val) {
              p.next = p1
              p = p1
              p1 = p1.next
          }else{
              p.next = p2
              p = p2
              p2 = p2.next
          }
      }
      if(p1!=null) p.next = p1
      else p.next = p2
      return vHead.next
  }

  function getLength(head:ListNode|null){
      let p = head
      let l = 1
      while(p!=null){
          p=p.next
          l++
      }
      return l
  }
  //开始啦
  if(head==null) return null
  const LEN = getLength(head)
  let vHead = new ListNode(-1)
  vHead.next = head
  for(let i=1;i<LEN;i*=2){
      let t = vHead               //用来连接后来形成的多段链表
      let p:ListNode|null = vHead.next
      while(p!=null){
          let h1 = new ListNode(-1)
          let p1 = h1
          let h2 = new ListNode(-1)
          let p2 = h2
          for(let j=0;j<i&&p!=null;j++){
              p1.next = p
              p1 = p
              p = p.next
          }
          p1.next = null
          for(let j=0;j<i&&p!=null;j++){
              p2.next = p
              p2 = p
              p = p.next
          }
          p2.next = null
          let merged = merge(h1.next,h2.next)
          t.next = merged
          while(t.next!=null) t=t.next

      }
  }
  return vHead.next
};


// 5606. 具有给定数值的最小字符串
function getSmallestString(n: number, k: number): string {
    //!搜索超时，只能贪心枚举每一位置
    let tmp =  new Array<number>(n)
    tmp.fill(1)
    let sum = n
    for(let i= n-1;i>=0&&sum<k;i--){
        let incr = (k-sum)/25>=1 ? 25 : k-sum
        tmp[i]+= incr
        sum += incr
    }
    const base = 'a'.charCodeAt(0)-1
    return tmp.reduce((pre,cur)=>pre+String.fromCharCode(base+cur),'')
};

// 5607. 生成平衡数组的方案数
function waysToMakeFair(nums: number[]): number {
    let oddFront:number[] = [0]
    let eventFront:number[] = [0]
    let oddBack:number[] = [0]
    let eventBack:number[] = [0]
    for(let i=1;i<nums.length;i++){
        //i是奇数位
        if(i&1){
            oddFront.push(oddFront[oddFront.length-1])
            eventFront.push(eventFront[eventFront.length-1]+nums[i-1])
        }else{
            eventFront.push(eventFront[eventFront.length-1])
            oddFront.push(oddFront[oddFront.length-1]+nums[i-1])
        }
    }

    for(let i=nums.length-2;i>=0;i--){
        //i是奇数位
        if(i&1){
            oddBack.push(oddBack[oddBack.length-1])
            eventBack.push(eventBack[eventBack.length-1]+nums[i+1])
        }else{
            eventBack.push(eventBack[eventBack.length-1])
            oddBack.push(oddBack[oddBack.length-1]+nums[i+1])
        }
    }

    oddBack.reverse()
    eventBack.reverse()

    let sum = 0

    for(let i=0;i<nums.length;i++){
        let odd  = oddFront[i] + eventBack[i] 
        let even = oddBack[i] + eventFront[i]
        if(odd==even) sum++
    }
    return sum
};
// 5608. 完成所有任务的最少初始能量
function minimumEffort(tasks: number[][]): number {
    tasks.sort((a,b)=>{
        let diff = (b[1]-b[0])-(a[1] - a[0])
        return diff !=0 ? diff : a[1] - b[1]
    })
    let total = 0
    let left = 0
    for(const [cost,need] of tasks){
        if(left<need){
            total+=(need-left)
            left = need
        }
        left -= cost
    }
    return total
};