#include <bits/stdc++.h>
using namespace std;

#define V vector
#define P pair

#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pair<int, int>>

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)

#define all(v) ((v).begin()), ((v).end())
#define sz(v) ((int)((v).size()))
#define endl '\n'

#define pb push_back

#define var auto

void radix_sort(vector<pair<pii, int>> &a) {
    int n = a.size();

    {
        vi cnt(n);
        for(var x : a) cnt[x.first.second]++;
        vi pos(n);
        pos[0] = 0;
        rep(i, 1, n) pos[i] = pos[i - 1] + cnt[i - 1];

        vector<pair<pii, int>> a_new(n);
        for(var x : a) {
            int i = x.first.second;
            a_new[pos[i]] = x;
            pos[i]++;
        }
        a = a_new;
        //a.swap(a_new);
    }

    {
        vi cnt(n);
        for(var x : a) cnt[x.first.first]++;
        vi pos(n);
        rep(i, 1, n) pos[i] = pos[i - 1] + cnt[i - 1];

        vector<pair<pii, int>> a_new(n);
        for(var x : a) {
            int i = x.first.first;
            a_new[pos[i]] = x;
            pos[i]++;
        }
        a = a_new;
    }
}

void suffixArray(string &s, V<vi> &allCnt) {

    s += (char)32;
    int n = s.size();
    vi sa(n);
    {
        vi c(n);
        vii a(n);
        rep(i, 0, n) a[i] = {s[i], i};
        sort(all(a));
        rep(i, 0, n) sa[i] = a[i].second;
        c[sa[0]] = 0;
        rep(i, 1, n) c[sa[i]] = c[sa[i - 1]] + (a[i].first != a[i - 1].first);
        allCnt.pb(c);
    }

    V<P<pii, int>> a(n);
    int k = 0;
    while((1 << k) < n) {
        var c = allCnt.back();
        rep(i, 0, n) a[i] = {{c[i], c[(i + (1 << k)) % n]}, i};
        radix_sort(a);
        rep(i, 0, n) sa[i] = a[i].second;
        vi new_c(n);
        new_c[sa[0]] = 0;
        rep(i, 1, n) new_c[sa[i]] = new_c[sa[i - 1]] + (a[i].first != a[i - 1].first);
        allCnt.pb(new_c);
        ++k;
    }
}

void getK(int n, vi &parts) {
    // 7 -> 4 -> 2 -> 1
    // 8 -> 8
    // 9 -> 8 -> 1
    // 10 -> 8 -> 2
    // 11 -> 8 -> 2 -> 1
    
    while(n) {
        int k = log(n) / log(2);
        parts.pb(k);
        n -= (1 << k);
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;
    
    int t;
    cin >> t;
    vii queries(t);
    int a, b;
    rep(i, 0, t) {
        cin >> a >> b;
        queries[i].first = a;
        queries[i].second = b;
    }

    V<vi> allCnt;
    suffixArray(s, allCnt);

    sort(all(queries), [allCnt] (pii &a, pii &b) {
        int l1 = a.second - a.first + 1;
        int l2 = b.second - b.first + 1;
        int min = l1 <= l2 ? l1 : l2;
        
        vi parts;
        getK(min, parts);

        int sum1 = a.first - 1;
        int sum2 = b.first - 1;
        rep(i, 0, parts.size()) {
            int k = parts[i];
            if(allCnt[k][sum1] != allCnt[k][sum2]) {
                return allCnt[k][sum1] < allCnt[k][sum2];
            }
            sum1 += (1 << k);
            sum2 += (1 << k);
        }
        
        if(l1 != l2) {
            return l1 < l2;
        }

        if (a.first != b.first) {
            return a.first < b.first;
        }

        return a.second <= b.second;
    });

    rep(i, 0, t) {
        cout << queries[i].first << " " << queries[i].second << endl;
    }

    return 0; 
}

import java.io.*;
import java.util.*;
 
public class P51 {
 
    public static void main(String[] args) throws IOException {
        Scanner io = new Scanner(System.in);
        int n = io.nextInt();
        long ans = (long) n * (n + 1) / 2;
        while (n-- > 1) {
            int a = io.nextInt();
            ans -= a;
        }
        System.out.println(ans);
    }
}

package com.onssoftware;

import java.io.*; import java.util.*;

public class A2_Uprooted {

public static Kattio io;

public static void main(String[] args) {

    io = new Kattio(System.in, System.out);

    int N = io.getInt();
    int M = io.getInt();
    int S = io.getInt();

    Map<Integer, List<Edge>> adjList = new HashMap<>();

    for (int index = 1; index <= M; index++) {

        int a = io.getInt();
        int b = io.getInt();
        int c = io.getInt();
        Edge e = new Edge(a, b, c, index);

        List<Edge> listA = adjList.getOrDefault(a, new ArrayList<>());
        listA.add(e);
        adjList.put(a, listA);

        List<Edge> listB = adjList.getOrDefault(b, new ArrayList<>());
        listB.add(e);
        adjList.put(b, listB);
    }

    int[][] sequences = new int[S][N - 1];
    for (int i = 0; i < S; i++) {
        for (int j = 0; j < N - 1; j++) {
            sequences[i][j] = io.getInt();
        }
    }

    new A2_Uprooted().solution(N, M, S, adjList, sequences);

    io.close();
}

public void solution(int n, int m, int s, Map<Integer, List<Edge>> adjList, int[][] sequences) {

    Map<Integer, Set<Edge>> nodeListMap = new HashMap<>();

    StringBuilder stringbuilder = new StringBuilder();

    for (int row = 0; row < s; row++) {

        Map<Integer, Boolean> nodeMap = new HashMap<>();
        // Node 1 is taken
        nodeMap.put(1, true);

        for (int column = 0; column < n - 1; column++) {

            int node = sequences[row][column];
            if (nodeMap.getOrDefault(node, false)) continue;

            //
            List<Edge> edgeList = adjList.getOrDefault(node, new ArrayList<>());
            Set<Edge> tempList = new HashSet<>();
            for (Edge edge : edgeList) {
                // Add node to existing set
                int neighbour = edge.getNeighbour(node);

                // If any of neighbours in the set, and if so, we consider it, add it to all existing edges
                if (nodeMap.getOrDefault(neighbour, false)) {
                    //tempList is the primary options
                    tempList.add(edge);
                }
            }

            // Fetch the old options from previous sequences
            Set<Edge> nodeListOld = nodeListMap.getOrDefault(node, new HashSet<>());
            // Check if any common branches. Then remove it. getCommon is a must have
            Set<Edge> nodeListCommon = getCommon(nodeListOld, tempList);


            // If there are no common branches, then its impossilbe
            if (nodeListCommon.isEmpty()) {
                io.println("IMPOSSIBLE");
                return;
            }

            // Saving the options to add nodes to existing vertices. Considering all common edges
            nodeListMap.put(node, nodeListCommon);

            // Add the new vertex into the nodemap
            nodeMap.put(node, true);
        }
    }

    List<Edge> edgeListFinal = new ArrayList<>();

    // Constructing the solutions
    for (Integer node : nodeListMap.keySet()) {
        Set<Edge> edgeList = nodeListMap.getOrDefault(node, new HashSet<>());
        if (edgeList.size() == 1) {
            edgeListFinal.addAll(edgeList);
        }
        else {
            Edge maxEdge = null;
            for (Edge e : edgeList) {
                if (maxEdge == null || maxEdge.c < e.c)
                    // Adding all the maximum edges.
                    maxEdge = e;
            }
            edgeListFinal.add(maxEdge);
        }
    }

    io.println(edgeListFinal.size());
    for (int i = 0; i < edgeListFinal.size() - 1; i++) {
        stringbuilder.append(edgeListFinal.get(i).index).append(" ");

        // io.print(edgeListFinal.get(i).index + " ");
    }
    io.print(stringbuilder.toString());
    io.println(edgeListFinal.get(edgeListFinal.size() - 1).index);
}

private Set<Edge> getCommon(Set<Edge> nodeListOld, Set<Edge> tempList) {

    if (nodeListOld.isEmpty()) return new HashSet<>(tempList);

    nodeListOld.retainAll(tempList);
    return nodeListOld;
}

}

class Edge { int a, b, c, index;

Edge(int a, int b, int c, int index) {
    this.a = a;
    this.b = b;
    this.c = c;
    this.index = index;
}

int getNeighbour(int one) {
    if (a == one) return b;
    return a;
}

}

class Kattio extends PrintWriter { private BufferedReader r; private String line; private StringTokenizer st; private String token;

public Kattio(InputStream i) {
    super(new BufferedOutputStream(System.out));
    r = new BufferedReader(new InputStreamReader(i));
}

public Kattio(InputStream i, OutputStream o) {
    super(new BufferedOutputStream(o));
    r = new BufferedReader(new InputStreamReader(i));
}

public boolean hasMoreTokens() {
    return peekToken() != null;
}

public int getInt() {
    return Integer.parseInt(nextToken());
}

public double getDouble() {
    return Double.parseDouble(nextToken());
}

public long getLong() {
    return Long.parseLong(nextToken());
}

public String getWord() {
    return nextToken();
}

private String peekToken() {
    if (token == null)
        try {
            while (st == null || !st.hasMoreTokens()) {
                line = r.readLine();
                if (line == null) return null;
                st = new StringTokenizer(line);
            }
            token = st.nextToken();
        } catch (IOException e) {
        }
    return token;
}

private String nextToken() {
    String ans = peekToken();
    token = null;
    return ans;
}

}