class Solution {
    public int removeDuplicates(int[] nums) {
        int cur = 0;
        for(int i = 1; i < nums.length; i++ ) {
            if(nums[i] != nums[cur]) nums[++cur] = nums[i];//如果当前nums[i]的值与已经存储的最后元素nums[cur]不等，则存入下一个位置, 第一个数肯定要
        }
        return cur+1;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        int cur = 0;
        for(int i = 0; i < nums.length; i ++) {
            if(nums[i] != 0) nums[cur++] =  nums[i];
        }

        //补零
        while ( cur < nums.length ) {
            nums[cur] = 0;
            cur ++;
        }
    }
}

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m -1, j = n -1, cur = m + n -1;
        while(i >= 0 || j >= 0) {
            if(j < 0 || (i >= 0 && nums1[i] >= nums2[j])){ // 在nums2已经越界或者i没越界且为大的时候，存入nums1[i]
                nums1[cur] = nums1[i];                
                i--;
            } else {
                nums1[cur] = nums2[j];
                j--;
            }
            cur--;
        }
    }
}

// 单链表
class MyLinkedListNode {
    int val;
    MyLinkedListNode next;
}

// 双链表
class MyDoubleLinkedListNode {
    int val;
    MyDoubleLinkedListNode next;
    MyDoubleLinkedListNode pre;
}


public static void main(String[] args) {
    // 具有保护节点的单链表 protect.next = head
    LinkedList protect = new LinkedList(0, null);

    // 

    // 具有保护节点组的双链表      
    LinkedList protectTail = new LinkedList(0, null);        
    LinkedList protectHead = new LinkedList(0, protectTail);
    protectTail.pre = proctedHead;
    protectedHead.pre = null;
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode last = null;
        while (head != null) {
            ListNode nextHead = head.next; // 缓存因为next会被修改
            head.next = last; // 跟新next指针
            last = head; //更新上一个节点为当前节点
            head = nextHead; // 更新当前节点 推进
        }

        return last;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
    ListNode protect = new ListNode(0, head);
    ListNode last = protect;
    while(head != null) {
        // 1. 分组：每k个元素的头尾节点确定
        ListNode groupEnd = getEnd(head, k);
        if(groupEnd == null) break;
        // 分组遍历逻辑
        ListNode cacheNexthead = groupEnd.next; // 后继结点会被跟新需要先缓存
        
        
        // 2. 子问题：针对每一组k个元素的反转问题
        reverseList(head, cacheNexthead);

        // 3. 每组k个元素的指向前一组tail，后一组head引用更新问题        
        last.next = groupEnd; // 前一组最后应指向本组的最后即变化后的头节点
        head.next = cacheNexthead; // 本组的最后一个节点应该指向下一组的head

         // 更新组头尾节点
            last = head; // last 应该指向调转后的head，groupEnd已经是新的链表头
            head = cacheNexthead; // head 应该指向下一组头节点
        }

        return protect.next;
    }

    public ListNode getEnd(ListNode head, int k) {
        while (head != null) {
            k--;            
            if(k == 0) return head;
            head = head.next; // 走k-1次，返回groupEnd
        }
        // 返回End, 但是复用LC206算法需要last.next
        return head;
    }

    public void reverseList(ListNode head, ListNode nextHead) {
        // 第一步跳过，因为第一个head的next会在第三步更新
        ListNode last = head;
        head = head.next;
        while (head != nextHead) {
            ListNode cacheNextHead = head.next; // 缓存因为next会被修改
            head.next = last; // 跟新next指针
            last = head; //更新上一个节点为当前节点
            head = cacheNextHead; // 更新当前节点 推进
        }
    }
}

import java.util.Arrays;
import java.util.Scanner;

// ACWing need a class called Main for solution
// and all the input/output logic
public class Main {

    public static void main(String args[]) {
        // input the array
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int i = 0;
        Node[] nums = new Node[size], sorted = new Node[size];
        int[] diff = new int[size-1], pre = new int[size-1];
        while(i < size){
            int number = sc.nextInt();
            Node node = new Node(number, i);
            nums[i] = node;
            sorted[i] = node;
            i++;
        }
        // sort and add pre/post information to build a linked list;
        Arrays.sort(sorted);
        for(int j = 0; j < sorted.length; j++){
            if(j > 0) sorted[j].pre = sorted[j-1]; else sorted[j].pre = new Node(Integer.MIN_VALUE, -1);
            if(j < nums.length -1) sorted[j].post = sorted[j+1]; else sorted[j].post = new Node(Integer.MAX_VALUE, size);
        }

        // start from last of array nums, calc it's pre/post diff via Linked List, and remove that node in linked list;
        while(i > 1){
            i--;
            int preDiff = nums[i].pre.index >= 0 && nums[i].pre.index < size ? nums[i].value - nums[i].pre.value : Integer.MAX_VALUE;
            int postDiff = nums[i].post.index >= 0 && nums[i].post.index < size ? nums[i].post.value - nums[i].value: Integer.MAX_VALUE;
            diff[i-1] = Math.min(preDiff, postDiff);
            if(preDiff <= postDiff) pre[i-1] = nums[i].pre.index+1;
            else pre[i-1] =  nums[i].post.index+1;
            removeNode(nums[i]);
        }

        print(diff, pre);
    }

    private static void print(int[] diff, int[] pre){
        for(int i = 0; i < diff.length; i++){
            System.out.println(diff[i] + " " + pre[i]);
        }
    }

    private static void removeNode(Node node){
        Node postCache = node.post;
        node.pre.post = postCache;
        node.post.pre = node.pre;
    }

    static class Node implements  Comparable<Node>{
        int value;
        int index;
        public Node pre;
        public Node post;

        public Node(int value, int index){
            this.value = value;
            this.index = index;
        }


        @Override
        public int compareTo(Node other) {
            return this.value - other.value;
        }
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        do {
            if(fast == null || fast.next == null) return false; 
            fast = fast.next.next; // 快指针每次走两步
            slow = slow.next; // 慢指针每次走一步
        }
        while(fast != slow);
        return true;
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        do {
            if(fast == null || fast.next == null) return null; 
            fast = fast.next.next; // 快指针每次走两步
            slow = slow.next; // 慢指针每次走一步
        }
        while(fast != slow);
        ListNode slow2 = head; 
        while (slow != slow2){ // 不能do while，因为有可能相遇的节点就正是环开始节点 [1, 2] 0
            slow = slow.next;
            slow2 = slow2.next;
        }
        return slow;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur1 = list1, cur2 = list2, nextHead2 = null, protect = new ListNode(0, list1),lastHead1 = protect;
        while(cur1 != null || cur2 != null) {           
            // 更新节点
            if(cur1 == null || (cur2 != null && cur1.val > cur2.val)){ // 取list2节点,cur2 推进
                // 先缓存即将推进的节点
                nextHead2 = cur2.next;
                // cur2 插入在cur1之前,lastHead1之后       
                cur2.next = cur1;               
                lastHead1.next = cur2;
                // 更新lastHead1 和cur2 指针          
                lastHead1 = cur2;
                cur2 = nextHead2;                
            } else { //取list1节点，cur1直接推进
                lastHead1 = cur1;
                cur1 = cur1.next;
            }
        }
        return protect.next;
    }
}

class Solution {
    public int[] plusOne(int[] digits) {
        // 逆序+递归
        return plusOne(digits, digits.length -1);
    }

    public int[] plusOne(int[] digits, int pos){
        if(pos == -1) {
            int[] result = new int[digits.length+1];
            result[0] = 1;
            for(int i = 0; i < digits.length; i ++){
                result[i+1] = digits[i];
            }
            return result;
        }
        digits[pos] += 1;
        if(digits[pos]/10 == 1) {
            digits[pos] %= 10;
            return plusOne(digits, pos-1);
        }
        return digits;
    }
}

class Solution {
    public int evalRPN(String[] tokens) {
            int cur = 0;
            Stack<Integer> nums = new Stack<>();
            while(cur < tokens.length){
                if(tokens[cur].equals("+") || tokens[cur].equals("-") || tokens[cur].equals("*")  || tokens[cur].equals("/")){
                Integer operant1 = nums.pop();
                Integer operant2 = nums.pop();
                nums.push(calculate(operant1, operant2, tokens[cur]));
            }else nums.push(Integer.parseInt(tokens[cur]));
                cur ++;
            }
            return nums.peek();
        }

        public Integer calculate(Integer x, Integer y, String operator){
            switch(operator)
            {
                case "+":
                    return x + y;
                case "-":
                    return y - x;
                case "*":
                    return x * y;
                case "/":
                    return y/x;
            }
            return 0;
        }
}

class Solution {
   public int calculate(String s) {
            s += " ";
            ArrayList<String> tokens = new ArrayList<>();
            Stack<Character> operators = new Stack<>();
            String number = "";
            boolean needsZero = true; // -4 * 9 需要补零
            for(int i = 0; i < s.length(); i ++){
                char ch = s.charAt(i);
                if (ch >= '0' && ch <= '9'){
                    number += ch;
                    needsZero = false; // 5-3 不需要补零
                    continue;
                } else if(!number.isEmpty()){
                    tokens.add(number);
                    number = "";
                }

                if (ch == ' ') continue;
                if (ch == '(') {
                    operators.push('(');
                    needsZero = true; // (-3) 需要补零
                    continue;
                }
               if (ch == ')') {
                    while (!operators.empty() && !operators.peek().equals('(')){
                        tokens.add(operators.pop().toString());
                    }
                    if (!operators.empty() && operators.peek().equals('(')){
                        operators.pop();// 不需要）
                    }
                    needsZero = false; // )-3 不需要补零
                    continue;
                }

                int currRank = getRank(ch);
                while (!operators.empty() && getRank(operators.peek()) >= currRank){
                    tokens.add(operators.pop().toString());
                }
                operators.push(ch);
                if(ch == '-' && needsZero) tokens.add(Integer.toString(0));
            }

            while (!operators.isEmpty()){
                tokens.add(operators.pop().toString());
            }

            return evalRPN(tokens);
        }

        public int getRank(char ch){
            if(ch == '+' || ch == '-' ) return 1;
            if(ch == '*' || ch == '/' ) return 2;
            return 0;
        }

        int evalRPN(ArrayList tokens){
            Stack<Integer> operants = new Stack<>();
            for(int i = 0; i < tokens.size(); i ++ ){
                String token = (String) tokens.get(i);
                if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")){
                    Integer operant1 = operants.pop();
                    Integer operant2 = operants.pop();
                    operants.push(calc(operant1, operant2, token));
                }else {
                    operants.push(Integer.parseInt(token));
                }
            }
            return operants.peek();
        }

        Integer calc(Integer x, Integer y, String token){
            if(token.equals("+")) return x +y;
            if (token.equals("-")) return y -x;
            if(token.equals("*")) return x *y;
            if (token.equals("/")) return y /x;
            return 0;
        }
}

class Solution {
   public int calculate(String s) {
            s += " ";
            ArrayList<String> tokens = new ArrayList<>();
            Stack<Character> operators = new Stack<>();
            String number = "";
            boolean needsZero = true; // -4 * 9 需要补零
            for(int i = 0; i < s.length(); i ++){
                char ch = s.charAt(i);
                if (ch >= '0' && ch <= '9'){
                    number += ch;
                    needsZero = false; // 5-3 不需要补零
                    continue;
                } else if(!number.isEmpty()){
                    tokens.add(number);
                    number = "";
                }

                if (ch == ' ') continue;
                if (ch == '(') {
                    operators.push('(');
                    needsZero = true; // (-3) 需要补零
                    continue;
                }
               if (ch == ')') {
                    while (!operators.empty() && !operators.peek().equals('(')){
                        tokens.add(operators.pop().toString());
                    }
                    if (!operators.empty() && operators.peek().equals('(')){
                        operators.pop();// 不需要）
                    }
                    needsZero = false; // )-3 不需要补零
                    continue;
                }

                int currRank = getRank(ch);
                while (!operators.empty() && getRank(operators.peek()) >= currRank){
                    tokens.add(operators.pop().toString());
                }
                operators.push(ch);
                if(ch == '-' && needsZero) tokens.add(Integer.toString(0));
            }

            while (!operators.isEmpty()){
                tokens.add(operators.pop().toString());
            }

            return evalRPN(tokens);
        }

        public int getRank(char ch){
            if(ch == '+' || ch == '-' ) return 1;
            if(ch == '*' || ch == '/' ) return 2;
            return 0;
        }

        int evalRPN(ArrayList tokens){
            Stack<Integer> operants = new Stack<>();
            for(int i = 0; i < tokens.size(); i ++ ){
                String token = (String) tokens.get(i);
                if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")){
                    Integer operant1 = operants.pop();
                    Integer operant2 = operants.pop();
                    operants.push(calc(operant1, operant2, token));
                }else {
                    operants.push(Integer.parseInt(token));
                }
            }
            return operants.peek();
        }

        Integer calc(Integer x, Integer y, String token){
            if(token.equals("+")) return x +y;
            if (token.equals("-")) return y -x;
            if(token.equals("*")) return x *y;
            if (token.equals("/")) return y /x;
            return 0;
        }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
            Stack<Rect> s = new Stack<>();
            int result = 0;
            for(int i = 0; i <= heights.length; i ++){
                int h = i == heights.length ? 0 : heights[i]; // 末尾补零，从而清空栈。
                int accumulatedWidth = 0;
                // 新的元素破坏单调性
                while(!s.isEmpty() && s.peek().height > h) {
                    accumulatedWidth += s.peek().width;
                    result = Math.max(result, s.peek().height * accumulatedWidth);
                    s.pop();
                }
                s.push(new Rect(accumulatedWidth + 1, h));
            }
            return result;
        }

        class Rect {
            int width;
            int height;

            Rect (int width, int height){
                this.width = width;
                this.height = height;
            }
        }
}

class Solution {
        public int trap(int[] heights) {
            int result = 0;
            for(int i = 0; i < heights.length; i++){
                int accumulatedWidth = 0;
                int height = heights[i];
                while(!s.isEmpty() && s.peek().height <= height) {
                    int bottom = s.peek().height;
                    accumulatedWidth += s.peek().width;
                    s.pop();
                    // 以bottom为底，accumulatedWidth为宽度，（左右两侧较小者）up为顶的长方形是累积的雨水横条
                    // 如果栈空，则高度为bottom，增加面积为0
                    int up = s.isEmpty() ? bottom : Math.min(height, s.peek().height);

                    result += accumulatedWidth * (up - bottom);
                }
                s.push(new Rect( accumulatedWidth + 1, height ));
            }
            return result;
        }

    class Rect {
        int width;
        int height;
        Rect(int width, int height){
                this.width = width;
                this.height = height;
            }
    }

    Stack<Rect> s = new Stack<>();
}

class Solution {
    public boolean isValid(String s) {
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == ')'){
                if(o.isEmpty() || !cleanUp("(")) return false;
            }else if(c == '}'){
                if(o.isEmpty() || !cleanUp("{")) return false;
            }else if(c == ']'){
                if(o.isEmpty() || !cleanUp("[")) return false;
            }else o.push(String.valueOf(c));
        }
        if(o.isEmpty()) return true;
        return false;
    }

    private boolean cleanUp(String match){
        while(!o.isEmpty()) {
            String x = o.pop();
            if(x.equals(match)) return true;
            else return false;
        }
        return false;
    }
    Stack<String> o = new Stack<>();
}

class MinStack {

    public MinStack() {

    }
    
    public void push(int val) {
        // 单调递减栈
        if(min.isEmpty() || (!min.isEmpty() && min.peek() >= val)) {
            min.push(val);
        }
        s.push(val);
    }
    
    public void pop() {
        if(s.pop().equals(min.peek())) min.pop();
    }
    
    public int top() {
        return s.peek();
    }
    
    public int getMin() {
        return min.peek();
    }

    // 单调递减栈
    private Stack<Integer> min = new Stack<>();
    // 原栈
    private Stack<Integer> s = new Stack<>();
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int[] result = new int[Math.max(nums.length - k + 1, 1 )];
            int cur = 0;
            for(int i = 0; i < nums.length; i ++){
                int number = nums[i];
                while(!q.isEmpty() && nums[q.peekFirst()] <= i - k) q.removeFirst();
                while(!q.isEmpty() && nums[q.peekLast()] < number) q.removeLast();

                q.add(i);
                // 单调递减队列，队首是最大值
                if(i >= k-1)  result[cur++] = nums[q.peekFirst()];
            }
        return result;
        }

        LinkedList<Integer> q = new LinkedList<>();
    }

class MyCircularDeque {

    public MyCircularDeque(int k) {
            q = new LinkedList<Integer>();
            capacity = k;
        }

        public boolean insertFront(int value) {
            if(q.size() == capacity) return false;
            q.addFirst(value);
            return true;
        }

        public boolean insertLast(int value) {
            if(q.size() == capacity) return false;
            q.addLast(value);
            return true;
        }

        public boolean deleteFront() {
            if(q.isEmpty()) return false;
            q.removeFirst();
            return true;
        }

        public boolean deleteLast() {
            if(q.isEmpty()) return false;
            q.removeLast();
            return true;
        }

        public int getFront() {
            return q.isEmpty()? -1 : q.peekFirst();
        }

        public int getRear() {
            return q.isEmpty()? -1 : q.peekLast();
        }

        public boolean isEmpty() {
            return q.isEmpty();
        }

        public boolean isFull() {
            return q.size() == capacity;
        }

        private LinkedList<Integer> q ;
        private int capacity;
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

class Solution {
    public int maximalRectangle(char[][] matrix) {
        // 构造纵向连续1和二维数组S[rows][cols]
        // S[p][] 是一组子矩阵的纵向柱状图，求出最大矩形
        // 遍历所有p，得出最大矩阵所包含的最大矩形
        int rows = matrix.length, cols = matrix[0].length;
        int[][] S = new int[rows+1][cols];
        int[] max = new int[rows];
        int ans = 0;
        for(int r = 0; r <= rows; r ++) {            
            for(int c = 0; c < cols; c++) {
                if( r == 0 || matrix[r-1][c] == '0') {
                    S[r][c] = 0;
                    continue;
                } else S[r][c] = S[r-1][c]+1;
            }
        }

            for(int r = 1; r <= rows; r++) {
                max[r-1] = largestRectangleArea(S[r]);
                ans = Math.max(ans, max[r-1]);
            }

        return ans;
    }

    public int largestRectangleArea(int[] heights) {
            Stack<Rect> s = new Stack<>();
            int result = 0;
            for(int i = 0; i <= heights.length; i ++){
                int h = i == heights.length ? 0 : heights[i];  // 末尾补零，从而清空栈。
                int accumulatedWidth = 0;
                // 新的元素破坏单调性
                while(!s.isEmpty() && s.peek().height > h) {
                    accumulatedWidth += s.peek().width;
                    result = Math.max(result, s.peek().height * accumulatedWidth);
                    s.pop();
                }
                s.push(new Rect(accumulatedWidth + 1, h));
            }
            return result;
        }

        class Rect {
            int width;
            int height;

            Rect (int width, int height){
                this.width = width;
                this.height = height;
            }
        }
}

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int[] s = new int[nums.length+1];
        s[0] = 0;
        int[] count = new int[nums.length+1];
        count[0] = 1;
        for(int i = 1; i < count.length; i ++) count[i] = 0;
        for(int i = 1; i <= nums.length; i++) {
            s[i] = s[i-1] + nums[i-1]%2;
            count[s[i]]++;
        }
        // 存入count[s[i]]的个数
        // s[i] - s[j] == k 等价于
        // count[s[i] - k] 的个数
        int result = 0;
        for(int i = 0; i < s.length; i ++ ) {
            if(s[i] >=k ) result += count[s[i] - k];
        }
        return result;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int[] s = new int[nums.length+1];
        s[0]=0;
        int[] preMin = new int[nums.length+1];
        preMin[0] = 0;
        for(int i = 0; i < nums.length; i++) {
            s[i+1] = s[i] + nums[i];
        }
        int result = -10000;
        // preMin 是前缀和最小值，那么s[i] - preMin[j]则为最大子数组和。
        for(int i = 1; i < s.length; i ++) {
            preMin[i] = Math.min(preMin[i -1], s[i]);
            // 更新最大和 = s[i] - preMin[i-1] 至少包含第i个元素
            result = Math.max(result, s[i] - preMin[i-1]);
        }

        return result;        
    }
}

class NumMatrix {

    public NumMatrix(int[][] matrix) {
        n = matrix.length;//row number;
        m = matrix[0].length; // col number;
        sum = new int[n+1][m+1];
        // 二维数组前缀和
        for(int i = 1; i <= n ; i ++){
            for(int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j-1] -sum[i-1][j-1]+ matrix[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        row1++;
        row2++;
        col1++;
        col2++;
        // 索引加一，符合前缀和数组1开头算法。
        return sum[row2][col2] - sum[row1-1][col2] - sum[row2][col1-1] + sum[row1-1][col1-1];
    }

    int sum[][];
    int n, m;
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] delta = new int[n+2];
        for(int i = 0; i < n+2; i ++) delta[i] = 0;
        for(int i = 0; i < bookings.length; i++){
            int[] booking = bookings[i];
            int first = booking[0];
            int last = booking[1];
            int seats = booking[2];
            delta[first] += seats; // += 纵向累加delta，seats是diff booking[][first] - booking[first-1]
            delta[last+1] += -seats;  // -seats 是 booking[]last+1] - booking[last] 
        }
        int[] sum = new int[n];
        for(int i = 0;i < n; i++) sum[i] = delta[1];
        for(int i = 1; i < n; i++){
            sum[i] =  sum[i-1] + delta[i+1];
        }
        return sum;
    }
}

/* O(m+n)
1  2  3  4  5
10   -10
   20   -20
   25
10 55 45 25 25
*/

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int j = numbers.length -1;
        for(int i = 0; i < numbers.length; i++) {
            while(i < j && numbers[i] + numbers[j] > target) j--;
            if(i < j && numbers[i] + numbers[j] == target) {
                return new int[]{i+1, j+1};
            }
        }
        return new int[]{};
    }
// O(n)
// 2 7 11 15 17 target = 18
// i         j 小于18停止左移动j，检查
//   i j     
//     i  j    小于18停止左移动j，检查
// i 移动时，j单调递减、递增。

}

class Solution {
    public int[] twoSum(int[] nums, int target) {
            Pair[] sorted = new Pair[nums.length];
            for(int i = 0; i < nums.length; i ++) sorted[i]= new Pair(i, nums[i]);
            Arrays.sort(sorted);
            int j = nums.length-1;
            for(int i = 0; i < nums.length; i++){
                while(i < j && sorted[i].value + sorted[j].value > target) j--;
                if(i < j && sorted[i].value + sorted[j].value == target) return new int[]{sorted[i].index, sorted[j].index};
            }
            return new int[]{};
        }
        

    static class Pair implements Comparable<Pair> {
        public final int index;
        public final int value;

        public Pair(int index, int value) {
            this.index = index;
            this.value = value;
        }

        @Override
        public int compareTo(Pair other) {
            //multiplied to -1 as the author need descending sort order
            return Integer.valueOf(this.value).compareTo(other.value);
        }
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);// 顺序不再重要
            List<List<Integer>> result = new ArrayList<>();
            for(int i = 0; i < nums.length; i++){
                if(i != 0 && nums[i] == nums[i-1]) continue;// 去除第一位重复
                List<List<Integer>> twoSumResults = twoSum(nums, i + 1, -nums[i]);
                for(List<Integer> twoSumResult : twoSumResults){
                    result.add(Arrays.asList(nums[i], twoSumResult.get(0), twoSumResult.get(1)));
                }


            }
            return result;
        }

        List<List<Integer>> twoSum(int[] nums, int start, int target) {
            List<List<Integer>> result = new ArrayList<>();
            int j = nums.length-1;
            for(int i = start; i < nums.length; i++){
                if(i != start && nums[i] == nums[i-1]) continue;// 去除第二位重复
                while(i < j && nums[i] + nums[j] > target) j--;
                if(i < j && nums[i] + nums[j] == target) {
                    List<Integer> finding = new ArrayList<>();
                    finding.add(nums[i]);
                    finding.add(nums[j]);
                    result.add(finding);
                }
            }
            return result;
        }
}

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length-1, ans = 0;
        while( i < j){
            ans = Math.max(ans, Math.min(height[i], height[j])* (j-i));
            // i j 两个指针相遇问题，如果height[i]较矮，则前进i寻找更高的，否则前进j
            if(height[i] < height[j]) i++; else j--;
        }
        return ans;
    }
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
        recur(nums,0);
        return ans;
    }

    void recur(int[] nums, int i){
        // 递归边界
        if(i == n) {
            ans.add(new ArrayList<>(chosen));// 不可加入引用必须复制副本
            return;
        }

        // i 不选
        recur(nums, i+1);

        // i 选中
        chosen.add(nums[i]);
        recur(nums, i+1);
        chosen.remove(chosen.size()-1);
    }


    private int n;
    List<Integer> chosen = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
}

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        recur(1);
        return ans;
    }

    void recur( int i){
        if(chosen.size() > k || chosen.size() + (n -i + 1) <k ) return; // *** 提早退出，剪枝，已经超过k个，或者剩下全选也不够k个
        // 递归边界
        if(i == n+1 ) {
            if(chosen.size() == k) ans.add(new ArrayList<>(chosen));// 不可加入引用必须复制副本
            return;
        }

        // i 不选
        recur(i+1);

        // i 选中
        chosen.add(i);
        recur(i+1);
        chosen.remove(chosen.size()-1);
    }


    private int n, k;
    List<Integer> chosen = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        this.n = nums.length;
        this.used = new boolean[n];
        recur(nums, 0);
        return ans;
    }
    
    void recur(int[] nums, int pos) {
        // pos 为选中的数字个数
        if(pos == n) {
            ans.add(new ArrayList<>(a));
            return;
        }

        for(int i = 0; i < n; i++) {
            if(!used[i]){
                a.add(nums[i]);
                used[i] = true;
                recur(nums, pos +1 );
                // 还原，从而其他递归分支可以继续计算。
                used[i] = false;
                a.remove(a.size()-1);
            }
        }
    }
    boolean[] used;
    List<Integer> a = new ArrayList<>();
    int n;
    List<List<Integer>> ans = new ArrayList<>();
}