Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Iahub recently has learned Bubble Sort, an algorithm that is used to sort a permutation…

  1. User

    Iahub recently has learned Bubble Sort, an algorithm that is used to sort a permutation with n elements a1, a2, ..., an in ascending order. He is bored of this so simple algorithm, so he invents his own graph. The graph (let's call it G) initially has n vertices and 0 edges. During Bubble Sort execution, edges appear as described in the following algorithm (pseudocode).

    procedure bubbleSortGraph()  
        build a graph G with n vertices and 0 edges  
        repeat  
            swapped = false  
            for i = 1 to n - 1 inclusive do:  
                if a[i] > a[i + 1] then  
                    add an undirected edge in G between a[i] and a[i + 1]  
                    swap( a[i], a[i + 1] )  
                    swapped = true  
                end if  
            end for  
        until not swapped   
        /* repeat the algorithm as long as swapped value is true. */   
    end procedure  
    

    For a graph, an independent set is a set of vertices in a graph, no two of which are adjacent (so there are no edges between vertices of an independent set). A maximum independent set is an independent set which has maximum cardinality. Given the permutation, find the size of the maximum independent set of graph G, if we use such permutation as the premutation a in procedure bubbleSortGraph. Input

    The first line of the input contains an integer n (2 ≤ n ≤ 105). The next line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n).

    Output

    Output a single integer — the answer to the problem.

    Examples

    Input

    3 3 1 2

    Output

    2

    Note

    Consider the first example. Bubble sort swaps elements 3 and 1. We add edge (1, 3). Permutation is now [1, 3, 2]. Then bubble sort swaps elements 3 and 2. We add edge (2, 3). Permutation is now sorted. We have a graph with 3 vertices and 2 edges (1, 3) and (2, 3). Its maximal independent set is [1, 2].

  2. DeepSeek Assistant

    We need to understand the graph construction. We run bubble sort on a permutation a of size n (distinct numbers from 1 to n). The bubble sort algorithm as described: repeat: swapped = false; for i from 1 to n-1: if a[i] > a[i+1] then add an undirected edge between a[i] and a[i+1] (the values, not the positions! note: the vertices are labelled by the numbers 1..n, which are the values in the permutation), then swap a[i] and a[i+1], set swapped = true. Continue until sorted.

    So graph G has vertices labeled 1..n. Edges are added each time a swap occurs, between the two values that are being swapped. Since swaps may happen multiple times, same pair may be swapped multiple times? In bubble sort, after swapping, the elements move. Could the same pair of values be swapped again later? Possibly yes, if after further passes they become adjacent again? But in bubble sort, once an element moves past another, they may not meet again? Actually, bubble sort moves larger elements to the right gradually. Typically, each pass bubbles the largest unsorted element to its correct position. The same pair of values can be swapped at most once? Let's analyze: Suppose we have two distinct values x and y. In bubble sort, comparisons happen between adjacent elements. If x and y are compared and found in wrong order (x > y) and they are swapped, then after swapping, y (the smaller) moves left and x moves right. Could they be compared again later? For them to be compared again, they would need to become adjacent again. In bubble sort, after swapping, the larger element moves right, and in subsequent passes it may continue moving right, while the smaller element moves left? Actually, consider two specific values a and b. Suppose initially a is to the left of b. If a > b, they will be swapped when they are adjacent. After swap, b is left of a. Then as the algorithm continues in the same pass, the pointer moves forward; we compare the next pair. In later passes, the algorithm will compare adjacent pairs again from left to right. Now b is left of a. Could they be swapped again? That would require b > a, which is false because b < a (since we swapped because a > b). So they won't be swapped again. However, could they become adjacent later if other elements move between them? Possibly they could be separated by other elements, but to be compared again they would need to become adjacent again. In bubble sort, elements move in one direction only: larger elements bubble to the right, smaller elements bubble to the left? Actually, bubble sort as described: each pass goes from i=1 to n-1; if a[i] > a[i+1], swap. This moves the larger element to the right. It doesn't move smaller elements left except as a consequence of swapping with larger neighbors. However, consider two values that were not originally swapped because they were in correct order initially (a < b). Could they become out of order later due to other swaps? Example: permutation [2,1,3]? Let's test: Initially [2,1,3]. i=1: 2>1, swap => add edge (2,1), becomes [1,2,3]. i=2: compare 2 and 3, no swap. Pass ends with swapped true. Next pass: i=1: 1<2 no swap; i=2: 2<3 no swap; done. So edge only between 2 and 1. That's only one swap.

    Now consider a more complex case: [3,1,2] from example. Pass1: i=1: 3>1, swap -> add edge (3,1), becomes [1,3,2]; i=2: 3>2, swap -> add edge (3,2), becomes [1,2,3]; swapped true. Pass2: i=1: 1<2; i=2: 2<3; done. So edges: (3,1) and (3,2). So pair (1,2) never directly swapped. So each swapped pair only appears once? Could a pair be swapped multiple times? Suppose we have [2,3,1]? Let's simulate: Pass1: i=1: 2<3 no swap; i=2: 3>1 swap -> add edge (3,1), becomes [2,1,3]; swapped true. Pass2: i=1: 2>1 swap -> add edge (2,1), becomes [1,2,3]; i=2: 2<3 no swap; swapped true. Pass3: no swaps. So edges: (3,1) and (2,1). So pair (2,3) never swapped. So indeed each unordered pair of values appears at most once in the swap sequence? Let's try to find a counterexample: [3,2,1] gives swaps: pass1: i=1: 3>2 swap -> edge (3,2) -> [2,3,1]; i=2: 3>1 swap -> edge (3,1) -> [2,1,3]; swapped true. pass2: i=1: 2>1 swap -> edge (2,1) -> [1,2,3]; i=2: 2<3; swapped true. pass3: no swaps. So edges: (3,2), (3,1), (2,1). So all three pairs swapped. So each unordered pair at most once? In [3,2,1], all three pairs appear. In [2,1,3]? We got only (2,1). In [1,3,2]? That would be pass1: i=1:1<3; i=2:3>2 swap -> edge (3,2); becomes [1,2,3]; pass2: no swaps. So only (3,2). So pattern: an edge between two numbers if and only if at some point they were adjacent and out of order (i.e., the larger one was to the left) before they become in order? But note that after swapping they become in order relative to each other, and they will never be out of order again. So each unordered pair of distinct numbers either gets swapped exactly once or never. So the graph G is exactly the set of pairs (x,y) such that during the bubble sort process, they are compared when they are adjacent and x > y (so they get swapped). But is it equivalent to the condition that in the initial permutation, the relative order of x and y is inverted (i.e., x appears before y but x > y)? Not exactly, because some inverted pairs might never be directly swapped if they are never adjacent during the process? For example, consider [3,1,2] as earlier: the inverted pairs are (3,1) and (3,2) and (1,2) is not inverted (1<2 and order 1 before 2? Actually initial permutation [3,1,2]: pairs: (3,1): 3>1 and 3 before 1 => inversion; (3,2): 3>2 and 3 before 2 => inversion; (1,2): 1<2 and 1 before 2 => not inversion. So inversions correspond to edges? (3,1) and (3,2) are edges, yes. But what about (2,1) in [2,1,3]? inversion (2,1) is inverted, and edge (2,1) appears. So it seems that edges are exactly the inversions? But what about [2,3,1]? Inversions: (2,1) is inversion? Check: 2>1 and 2 appears before 1? Yes, 2 at position1, 1 at position3 => inversion; (3,1): inversion; (2,3): not inversion because 2<3 and order 2 before 3. Edges we got: (3,1) and (2,1). So (2,1) is inversion, edge appears; (3,1) inversion, edge appears; (2,3) not inversion, no edge. So indeed edges correspond to all inverted pairs? But wait, consider [4,2,3,1]? Let's simulate to see if all inversions become edges. Inversions: all pairs (i,j) with i<j and a[i] > a[j]. With permutation 4,2,3,1:

    • (4,2) inverted
    • (4,3) inverted? 4>3 and 4 before 3 -> yes.
    • (4,1) inverted
    • (2,3): 2<3, not inverted.
    • (2,1): 2>1 and 2 before 1 -> inverted.
    • (3,1): 3>1 inverted. Total inversions: (4,2),(4,3),(4,1),(2,1),(3,1) = 5.

    Now simulate bubble sort: Initial: [4,2,3,1] Pass1: i=1: 4>2 swap -> add edge (4,2), becomes [2,4,3,1] i=2: 4>3 swap -> add edge (4,3), becomes [2,3,4,1] i=3: 4>1 swap -> add edge (4,1), becomes [2,3,1,4] (after i=3) swapped true. Pass2: i=1: 2<3 no swap i=2: 3>1 swap -> add edge (3,1), becomes [2,1,3,4] (after i=2) i=3: 3<4 no swap swapped true. Pass3: i=1: 2>1 swap -> add edge (2,1), becomes [1,2,3,4] i=2: 2<3 no swap i=3: 3<4 no swap swapped true. Pass4: no swaps. Edges: (4,2),(4,3),(4,1),(3,1),(2,1). That's exactly all inversions. So seems edges = inversions.

    But is it always true? Let's test another: [3,4,2,1]? Initial inversions: (3,2),(3,1),(4,2),(4,1) maybe also (2,1)? Actually (2,1) if order? Let's list: positions:1:3,2:4,3:2,4:1. Pairs: (3,4): 3<4 not inversion. (3,2): inversion (3>2) (3,1): inversion (4,2): inversion (4>2) (4,1): inversion (2,1): inversion (2>1) So total 5 inversions. Simulate bubble sort: [3,4,2,1] Pass1: i=1: 3<4 no swap. i=2: 4>2 swap -> edge (4,2) => [3,2,4,1] i=3: 4>1 swap -> edge (4,1) => [3,2,1,4] swapped true. Pass2: i=1: 3>2 swap -> edge (3,2) => [2,3,1,4] i=2: 3>1 swap -> edge (3,1) => [2,1,3,4] i=3: 3<4 no swap. swapped true. Pass3: i=1: 2>1 swap -> edge (2,1) => [1,2,3,4] i=2: 2<3 no swap. i=3: 3<4 no swap. swapped true. Pass4: no swaps. Edges: (4,2),(4,1),(3,2),(3,1),(2,1). That's all inversions. So pattern holds.

    But is it always that every inversion becomes an edge? Intuitively, bubble sort compares adjacent elements and swaps if out of order. Each inversion will be "resolved" by a series of swaps that move the larger element to the right and the smaller to the left. For any inversion (x,y) where x > y and x appears before y, eventually x must move right past y, and at some point they become adjacent and get swapped. That swap adds the edge (x,y). So yes, every inversion yields an edge. Could there be an edge between a non-inverted pair? That would require they be swapped even though they are in correct order? That never happens because swap condition is a[i] > a[i+1]. So only if they are out of order, i.e., larger before smaller. So edge corresponds to a pair that was compared when they were adjacent and out of order. That implies that at that moment the larger is left of smaller. That is exactly an inversion at that moment. But could a pair be out of order at the time of comparison even if they were not inverted initially? For them to be out of order at that moment, the larger must be left of smaller. Since relative order can change due to swaps, it's possible that a pair that was initially not inverted becomes inverted later? Consider two numbers x and y with x < y. Initially x might be left of y. But later, could x move to the right of y? In bubble sort, larger elements move right; smaller elements can move left because they get swapped with larger elements. For example, if x is small, it might get swapped with a larger element on its left? Actually, consider x=1, y=2 initially [1,2,...]. Could they ever become out of order? For 1 to be to the right of 2, you'd need 2 to move left past 1, but bubble sort only swaps when left > right, so larger moves right, smaller moves left. So 2 cannot move left because it's larger than 1, but if 2 is left of 1, that's an inversion, so they'd be swapped to correct order. If initially 1 is left of 2, then they are in correct order; later, could they become out of order? Possibly if some other elements cause 2 to move left? No, swaps only happen when left > right, so the left element moves right if it's larger; the right element moves left if it's smaller. So a larger element never moves left; a smaller element never moves right? Actually, consider a smaller element that is on the left; if it encounters an even smaller element to its right, then left > right? No, if left is smaller than right, no swap. So a smaller element never moves right because to move right it would need to be swapped when it is on the left and greater than the right, but that would mean it's larger. So smaller elements can only move left when swapped with a larger element to its left? Check: If we have [3,1], 3>1, swap => 1 moves left? Actually 1 was on right, after swap it moves left (to position1). So smaller elements can move left when a larger element on left swaps with them. Smaller elements can move left, but cannot move right because they would need to be swapped as the left element with a smaller right element? That would be left > right, but left would be smaller? Actually if left is smaller and right is even smaller, left might be > right? If left=2, right=1, then left>right so they'd swap; that moves left (2) right? Actually 2 moves right? Wait: In a swap, we exchange positions. So if left=2, right=1, then after swap: positions: left becomes 1, right becomes 2. So 2 moved right. So a larger number moves right, a smaller moves left. So a small number can move left if it is on the right and the left neighbor is larger. But a small number that is on the left cannot move right because to move right it would need a smaller neighbor on the right, which would cause swap and it would move left? Actually, let's track: suppose small number s is on left, and to its right is an even smaller number t (t < s). Then at comparison, s > t, so swap, s moves right, t moves left. So s (which is small but larger than t) moves right! So small numbers can move right if they are larger than the element to their right. So they can move in both directions? Actually, any element moves right when it is the larger in a comparison, and moves left when it is the smaller. So both large and small can move either direction depending on relative ordering. So the dynamics are more complex. However, it's known that bubble sort will eventually sort by repeatedly swapping adjacent inversions. It is also known that each inversion is resolved exactly once by swapping the two elements when they become adjacent. So for any inversion (i,j) with i<j and a[i] > a[j], at some point during bubble sort, these two elements will be adjacent and swapped. That swap adds an edge between them. So edges = set of all inversions. But is it possible that a non-inverted pair (i.e., x<y and x appears before y) ever get swapped? That would require them to be out of order at some point, meaning at that moment x > y and x is left of y. But initially x<y and x left of y. Could they later become reversed? For them to become reversed, x would have to move to the right of y, or y move to left of x. Could that happen? Suppose initially ...x...y... with x<y. Could later x end up after y? That would mean they have crossed. For crossing to happen, there must be some intermediate swaps. Since bubble sort only swaps adjacent inversions, crossing would require x and y to be swapped at some point, which would happen only if they become adjacent with x > y. But if x<y, then to get x > y we need x to become larger than y? Impossible because values are fixed. So crossing would require that at the moment of swap, we have the larger element left, smaller right. Since x<y, the only way they could be swapped is if y (the larger) is left of x (the smaller), i.e., they are in opposite order. But that would mean initially y is before x, which is not the case (we assumed x before y). So they cannot become reversed because that would require y to overtake x from left to right, but that would mean y is larger and moving right? Actually, in bubble sort, larger elements move right, smaller move left. So y is larger than x, so it tends to move right. Starting from x before y, y is to the right of x. As the process goes, y might move further right, x might move left. They will not cross because crossing would require y to move left past x or x to move right past y. For y to move left past x, y would have to be on the right and then move left, but larger elements only move right, so they cannot move left. So y cannot move left. For x to move right past y, x is smaller, but could it move right? Yes, if x is larger than some element to its right, it could move right. But to pass y, x would have to become to the right of y. That would require at some point x and y being adjacent with x on left and x > y? But x < y, so that can't happen. Or if y moves left? Not possible. So crossing can't happen. So non-inverted pairs never become adjacent out of order, hence never swapped. So indeed edges are exactly the inversions.

    Thus graph G is the inversion graph (also known as permutation graph) of the given permutation. In an inversion graph, vertices are numbers 1..n, and there is an edge between i and j if and only if (i<j and permutation has i after j?) Wait careful: Vertices are labeled by the values, which are distinct numbers from 1 to n. The permutation arranges these values in some order. The condition for an edge between two values x and y (x != y) is that in the permutation, the relative order of x and y is inverted compared to their natural order (i.e., if x > y and x appears before y). So edge if and only if (x > y and pos(x) < pos(y)) or (x < y and pos(x) > pos(y)). Equivalently, if the order in the permutation and the numeric order disagree.

    This is exactly the comparability graph? Actually it's the permutation graph. A permutation graph is defined by a permutation π on {1,...,n} where vertices are numbers, and there is an edge between i and j if i < j and π^{-1}(i) > π^{-1}(j) (i.e., they are reversed in the permutation). That matches our situation if we interpret the permutation as the order of the values in the array. Usually the permutation graph is defined with vertices corresponding to the numbers 1..n, and an edge between i and j if i < j and π(i) > π(j) when considering positions as numbers? There are two equivalent representations. In our case, we have permutation a[1..n] which gives the order of the values. So we can think of positions 1..n and values a[i]. Then for two values u and v, we have edge if (u < v and pos(u) > pos(v)) OR (u > v and pos(u) < pos(v)). That's exactly the definition of the inversion graph (or permutation graph). So G is a permutation graph.

    Now we are asked to find the size of the maximum independent set (MIS) of this graph. In a permutation graph, there are known properties: The complement of a permutation graph is also a permutation graph, and the maximum independent set corresponds to the longest increasing subsequence (LIS) of the permutation? Let's recall: In a permutation graph, the vertices are points (i, π(i))? Actually typical representation: Place points at coordinates (i, π(i)). Then edges exist between points if the segments connecting them intersect when drawn in a certain way? More precisely, a permutation graph can be represented by a permutation π: For each i from 1 to n, we have a point (i, π(i)). Then there is an edge between i and j (i<j) if and only if (i-j)*(π(i)-π(j)) < 0, i.e., they form an inversion. That matches: if i<j and π(i) > π(j), they are inverted, and we draw an edge. So the graph's vertices are the indices (or the numbers) but we label vertices by the numbers 1..n. In our case, we have values as vertices, and positions are given by the permutation. Let's formalize: Let pos[v] = position of value v in the array a (1-indexed). Then for two values u<v, we have edge if and only if pos[u] > pos[v] (since u<v but if pos[u] > pos[v] then they are inverted). So the graph is exactly the inversion graph defined by the permutation of positions given by the values order? Actually if we list values in order of increasing position, we get the permutation of values. So define an ordering of values by positions: the sequence a[1], a[2], ..., a[n] is a permutation of 1..n. Then the condition for edge between u and v (with u<v) is that u appears after v in this sequence, i.e., pos[u] > pos[v]. So the graph edges correspond to inversions in the permutation when reading values in order of positions.

    Now, independent set: No two vertices are adjacent, i.e., no edge between any pair. That means for any two vertices u and v in the independent set, we cannot have an inversion between them. So for any u<v in the set, we must have pos[u] < pos[v] (since if u<v and pos[u] > pos[v], they'd be adjacent). Also for u>v? Actually if we take any two distinct vertices, we can order them by value. So condition: For all pairs (u,v) with u<v in the set, we must have pos[u] < pos[v]. That is exactly that the set of values is such that their positions are increasing with respect to the values. In other words, the values in the independent set, when sorted by their value, have positions that are strictly increasing. That's equivalent to saying that the values form a subsequence of the permutation that is increasing in terms of values? Wait, we sort by value and require positions increasing. That is exactly the condition for the sequence of values to be an increasing subsequence in the permutation? Actually, consider the permutation a (sequence of values). An increasing subsequence is a set of indices i1 < i2 < ... < ik such that a[i1] < a[i2] < ... < a[ik]. Here we have values v1 < v2 < ... < vk and we require pos[v1] < pos[v2] < ... < pos[vk]. That means if we look at the positions in order of increasing value, they are increasing. But note that if we take the permutation as list of values in order of positions, then the condition that values are increasing and positions are increasing is exactly that the subsequence of values (ordered by positions) is increasing. Because if we take positions p1 = pos[v1], p2 = pos[v2], ..., with v1<v2<... and p1<p2<..., then the values at positions p1,p2,... are v1,v2,... which are increasing. So that's an increasing subsequence of the permutation a. Conversely, any increasing subsequence of a gives a set of values (the values themselves) that satisfy v1<v2<... and positions are increasing. So there is a one-to-one correspondence between independent sets in the inversion graph and increasing subsequences of the permutation? Not exactly, because an independent set is just a set of vertices with no edges. The condition we derived: for any two vertices in the set, if u<v then pos[u] < pos[v]. This is equivalent to the set being a chain in the partial order defined by (value, position) where we order by both value and position? Actually it's equivalent to the set being both value-wise and position-wise consistent. That is exactly that the set corresponds to an increasing subsequence: pick indices (positions) such that the values are increasing. So the set of values corresponds to an increasing subsequence of the permutation. However, is the reverse true: does any increasing subsequence produce an independent set? Yes, because if we have indices i1 < i2 < ... < ik with a[i1] < a[i2] < ... < a[ik], then take the values S = {a[i1],...,a[ik]}. For any two values u<v in S, their positions are such that the position of u (the smaller value) must be before the position of v? Not necessarily: Since u appears as some a[ix] and v as a[iy] with u<v, but we know that the values are increasing with index: because ix < iy implies a[ix] < a[iy]? Actually we have ix < iy and a[ix] < a[iy], so if u = a[ix] and v = a[iy], then indeed u<v and pos[u] = ix < iy = pos[v]. But could there be a pair where u<v but pos[u] > pos[v]? That would contradict the fact that the subsequence is increasing because if we take the two elements in the subsequence, their order in the permutation is increasing index, and the values are increasing. So no. So indeed S is independent.

    Thus maximum independent set size equals the length of the longest increasing subsequence (LIS) of the permutation a. But is that always true? Let's verify with examples: Example given: n=3, a=[3,1,2]. The LIS of [3,1,2] is of length 2? The increasing subsequences: [1,2] length2, also [3]? Actually [1,2] from positions 2 and 3, [3] length1. So LIS length = 2. The answer output is 2. So matches. Another test: Suppose permutation [1,2,3]: LIS=3. Graph has no edges (since no inversions). Maximum independent set = all vertices =3, which matches LIS. Suppose [2,3,1]: LIS? increasing subsequences: [2,3] length2, [2]?, [3]?, [1]?, [2,1] not increasing. Actually [2,3] length2; also [2]? etc. So LIS length=2. Graph edges: (2,1) and (3,1). So independent set: can we take {2,3}? They are not adjacent? Check: 2 and 3: are they adjacent? Condition: 2<3, pos[2]=1, pos[3]=2, so pos[2] < pos[3] so no edge. Actually wait: In this permutation, 2 and 3 are in order (2 before 3, both less than each other? Actually 2<3 and pos[2] < pos[3], so they are not inverted, so no edge. So {2,3} is independent set size 2. Could we have {1,2}? 1 and 2: 1<2? but pos[1]=3 > pos[2]=1, so inversion, edge exists. So not independent. {1,3}: 1<3, pos[1]=3 > pos[3]=2, edge exists. So max independent set size=2, matches LIS. Suppose [3,2,1]: LIS length=1 (any single). Graph is complete (all pairs edges). So independent set max size 1. So matches.

    Thus answer = length of longest increasing subsequence (LIS) of the given permutation.

    But is that always correct for any n up to 1e5? Yes, LIS can be computed in O(n log n). However, careful: The graph's vertices are values, and independence condition as derived: for any two vertices u and v, no edge means not (u<v and pos[u] > pos[v]) and not (u>v and pos[v] > pos[u]) which is equivalent to (u<v => pos[u] < pos[v]) OR we can think of total order: the mapping from values to positions must be monotonic increasing on the set. That is equivalent to the set being a chain in the partial order where we compare by both value and position. In other words, the set's values are in increasing order and their positions are also increasing. That's exactly the same as an increasing subsequence in the permutation.

    But wait: Could there be an independent set that does not correspond to an increasing subsequence? Suppose we pick values that are not increasing? The condition must hold for all pairs. So if we pick values v1, v2, v3, ... we can sort them by value. After sorting, we need positions increasing. That's exactly the condition. So the set of values is an increasing subsequence. Because if we list them in order of positions, we may get a different ordering? But the condition implies that if we order by value ascending, positions are ascending. Also if we order by positions ascending, then values must be ascending (if positions ascending and values not ascending, then there would exist two with pos[u] < pos[v] but u>v, causing edge). So the set is both increasing in value when ordered by position and increasing in position when ordered by value. So it's an increasing subsequence.

    Thus maximum independent set size equals the length of the longest increasing subsequence.

    But wait: In a permutation graph, the maximum independent set is equal to the length of the longest increasing subsequence (LIS) and the maximum clique is equal to the length of the longest decreasing subsequence (by Dilworth's theorem or by properties of permutation graphs). Yes, that's a known fact: For a permutation graph, the size of a maximum independent set is the length of the longest increasing subsequence of the permutation. Because the graph is the inversion graph, an independent set corresponds to a set of points with no inversions, i.e., an increasing sequence.

    Therefore answer = LIS length.

    But before finalizing, we must double-check the graph construction carefully: The pseudocode adds an undirected edge between a[i] and a[i+1] when swapping. But note that a[i] and a[i+1] are the values at that moment, and after swapping they exchange positions. Could there be an edge added between two values that are not inverted in the final sense? Consider a scenario where two values are swapped but they are not an inversion in the original permutation? For example, could a swap occur between two values that originally were in correct order but due to previous swaps they become out of order? As argued earlier, that would imply crossing of a non-inverted pair. Let's try to construct a counterexample. Start with [2,1,3] we saw edges only (2,1). That's inversion. Try a longer permutation: [2,3,1,4]. Simulate: pass1: i=1:2<3 no swap; i=2:3>1 swap edge(3,1) -> [2,1,3,4]; i=3:3<4 no swap. pass2: i=1:2>1 swap edge(2,1) -> [1,2,3,4]; pass3 no swaps. Edges: (3,1) and (2,1). Inversions originally: (2,1), (3,1) (since 2>1,3>1) and (2,3) is not inverted because 2<3. So edges match inversions. So it seems always edges are exactly inversions.

    But is there any scenario where two values that are originally not inverted become inverted later? That would require a larger value to move left past a smaller value. Larger values only move right (since they only swap when they are left and greater than right). So a larger value never moves left. A smaller value could move left or right. Could that cause a new inversion? Suppose we have x < y and initially x left of y (pos x < pos y). For them to become inverted, we need y left of x (pos y < pos x). Since y cannot move left, the only way is for x to move right past y. Could x move right past y? To move right, x must be larger than some element to its right and swap. At some point, x could move right while y stays? But to pass y, they must become adjacent with x on left and x > y? But x < y, so x is never larger than y. So that adjacency with x left and x>y cannot occur. Could x and y be swapped indirectly through a chain? For x to get to the right of y, there must be a moment when they are adjacent and swapped. Since swap only occurs if left > right, if x is left of y, we would need x > y, which is false. So they will never swap. Therefore non-inverted pairs never become adjacent out of order. So edges only for original inversions. So our conclusion stands.

    Thus answer is LIS.

    Now we must compute LIS for n up to 1e5. Classic algorithm: maintain an array dp where dp[len] = smallest possible tail value of an increasing subsequence of length len. Iterate through a[i] (values in order of positions). For each x = a[i], find the largest len such that dp[len] < x (strictly increasing), then set dp[len+1] = x (or use lower_bound in dp for x for non-decreasing?). For strictly increasing subsequence, we need dp[len] < x. Usually we binary search for first element >= x and replace it to get LIS length for non-decreasing? Actually for strictly increasing, we want to maintain dp array where dp[i] is the smallest possible last element of an increasing subsequence of length i. Then for each x, we find the position where dp[pos] >= x (since we want to place x into the dp array such that for each length, the tail is minimized). For strictly increasing, we replace the first element >= x with x. The length of LIS is the size of dp after processing. This yields O(n log n). That's fine.

    But careful: The permutation values are from 1 to n distinct, so strictly increasing is natural.

    Now check: Example: n=3, a=[3,1,2]. Process: dp empty. x=3: find lower_bound(dp.begin(),dp.end(),3) => end, so push 3 => dp=[3]. x=1: lower_bound >=1 -> index0, dp[0]=1 => dp=[1]. x=2: lower_bound >=2 -> dp[1]? Actually dp=[1]; lower_bound returns index1 (end) because 2 > 1, so push => dp=[1,2]. length=2. Good.

    Now, ensure answer fits in int? n up to 1e5, output length up to n.

    Thus solution: read n, read permutation a, compute LIS length, output.

    But wait: Problem might be trickier? Let's think about if the graph is built as described, but note that vertices are the values, not indices. And we add edges between a[i] and a[i+1] at the moment of swap. However, after swapping, the array changes, and later swaps could involve different pairs. But as argued, edges correspond to inversions. However, there is nuance: The graph is built with vertices labelled by the numbers 1..n. When we add an edge between a[i] and a[i+1], we are adding edge between those values. Since values are unique, edges are between distinct values. Could it be that multiple edges are added between the same pair? Possibly if the same pair is swapped more than once? But we argued it's at most once. But what about a scenario where two values are swapped, then later after some movements, they become adjacent again but in opposite order? That would require them to be out of order again. But after swapping, they are in correct relative order (smaller left, larger right). Since larger never moves left, they can't become out of order again. So no.

    Thus graph is simple.

    Now confirm with known property: Bubble sort adds an edge for each swap, and the total number of swaps equals number of inversions. So edges = number of inversions. So the graph is exactly the inversion graph.

    Therefore answer is LIS length.

    But wait: There is also a possibility of the graph being defined differently: "add an undirected edge in G between a[i] and a[i+1]" where a[i] and a[i+1] are the values currently at those positions. Since values are numbers, it's fine.

    Double-check with small n=2: permutations: [2,1] => edges: (2,1). Graph has one edge. Maximum independent set size = 1. LIS length of [2,1] is 1. Yes. [1,2] => no edges, independent set size = 2, LIS=2. Good.

    Thus answer is LIS.

    Now we must write solution accordingly.

    But before finalizing, let's reflect if there is any twist: The problem statement says: "Given the permutation, find the size of the maximum independent set of graph G, if we use such permutation as the premutation a in procedure bubbleSortGraph." It might be that they ask for the size of maximum independent set after the graph is constructed. We argued it's LIS. But could there be any nuance that the graph built by bubble sort is not exactly the inversion graph because edges are added only when swaps happen, and swaps happen only when the two elements are adjacent and out of order. However, every inversion will eventually become adjacent and be swapped, so yes. So answer is LIS.

    Now let's try to prove more formally: For any inversion (i,j) where i<j and a[i] > a[j], during bubble sort, the larger element a[i] will move right until it passes a[j] and eventually they become adjacent and are swapped. This adds the edge. For any non-inverted pair, they never become swapped, so no edge. So edges = inversions.

    Given that, the graph is the comparability graph? It's the permutation graph. Maximum independent set in a permutation graph equals the size of the longest increasing subsequence. This is a classic result.

    We can also reason directly: A set S of vertices is independent iff for any two values u<v in S, pos[u] < pos[v]. That is exactly that the sorted-by-value sequence of positions is increasing. That implies that if we list the values in the order of positions (i.e., the permutation order), the values that appear are increasing when restricted to S. So S corresponds to an increasing subsequence. And any increasing subsequence yields such an S. So maximum independent set size = length of longest increasing subsequence.

    Thus solution is to compute LIS length.

    But wait: There is also the concept of "maximum independent set" in a graph that may not be the same as the maximum size of an increasing subsequence if the graph had extra edges. But we established that graph is exactly the inversion graph.

    Now, let's check constraints: n up to 10^5. LIS O(n log n) is fine.

    One nuance: The permutation a may contain numbers from 1 to n, but not necessarily that the array is a permutation of 1..n? Actually input says: n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n). Since they are distinct and in range 1..n, it is a permutation of 1..n. So yes.

    Thus solution is straightforward.

    But before coding, we should test with some edge cases:

    1. n=100000, sorted ascending => LIS=n => answer n. Graph has no edges, independent set size n. That's plausible.

    2. n=100000, sorted descending => LIS=1 => answer 1. Graph is complete, independent set max size 1.

    3. Random permutations: LIS length around 2*sqrt(n) for random, but okay.

    Now, ensure that we don't need to handle the graph building explicitly. It's not necessary.

    Thus code: read n, read array a (size n). Compute LIS length using std::vector dp; for each x in a: auto it = lower_bound(dp.begin(), dp.end(), x); if (it == dp.end()) dp.push_back(x); else *it = x; Output dp.size().

    But careful: For strictly increasing subsequence, we need to replace the first element >= x. That's correct. But sometimes LIS algorithms for strictly increasing use lower_bound on dp where dp stores the smallest tail for length i, and dp is maintained such that it's increasing. For each x, we find first dp[i] >= x and set dp[i] = x. This yields length of LIS. Yes.

    Let's test on [2,2]? Not allowed because distinct numbers. So okay.

    Now, is there any possibility that the independent set size is not the LIS length due to the graph having multiple edges or something? No.

    Double-check with more examples: [4,1,3,2]? Inversions: (4,1),(4,3),(4,2),(3,2) also (1,? ) none. So edges: 4-1,4-3,4-2,3-2. Graph: 4 connected to all; 3 connected to 4 and 2; 1 connected to 4; 2 connected to 4 and 3. Independent sets: maximum? Let's see possible independent sets: {1,3}? Check edge between 1 and 3? No edge, so ok. {1,2}? Edge? 1-2? No direct edge, but check: 1<2? pos[1]=2, pos[2]=4, so 1<2 and pos[1] < pos[2], so no inversion, thus no edge. So {1,2} is independent? Wait, check edges: edges list: (4,1), (4,3), (4,2), (3,2). So there is no edge (1,2). So {1,2} is independent. Also {1,3} no edge, {3}? etc. Largest? Could we have {1,2,?} plus maybe? {1,2,?} cannot include 3 because 3 is connected to 2, and 4 is connected to both 1 and 2. So max independent set size = 2? But maybe {1,3} size2, {2}? Actually {1,2} size2, {1,3} size2, {3}? What about {2} alone? So max = 2. Now LIS of [4,1,3,2]: increasing subsequences: [1,3] length2, [1,2] length2, [4]? [3]? So LIS length=2. So matches.

    Another: [3,4,1,2]. Inversions: (3,1),(3,2),(4,1),(4,2). Also (3,4) no; (1,2) no. Edges: 3-1,3-2,4-1,4-2. Independent sets? {3,4}? Check edge? 3<4 and pos[3]=1, pos[4]=2, so no edge. {3,4} is independent. {1,2}? 1<2, pos[1]=3, pos[2]=4, no edge, so {1,2} independent. {3,1}? edge, no. {3,2}? edge, no. {4,1}? edge, no. {4,2}? edge, no. Could we have {3,4,?} plus? Can't add 1 or 2 because they are connected to both 3 and 4? Actually 1 is connected to 3 and 4, so cannot add. 2 similarly. So max size 2. LIS: [3,4] length2, [1,2] length2, [3]? So LIS=2. Good.

    Another: [2,4,1,3]. Inversions: (2,1), (4,1), (4,3) maybe also (2,? ) 2<4 no, 2<3? pos2=1, pos3=4, 2<3 and pos2<pos3, so no; (4,? ) 4>1,4>3; also (1,3) 1<3 and pos1=3, pos3=4 -> pos1<pos3, so no. So edges: 2-1,4-1,4-3. Independent sets? Could we have {2,3,?}? Check 2 and 3: 2<3, pos2=1, pos3=4 => no edge. 2 and 1 edge, so cannot have 1. 3 and 4 edge, so cannot have 4. So {2,3} is independent size2. Could we have {1,?}? 1 with 2 or 4 edges, with 3? 1<3? pos1=3, pos3=4, pos1<pos3, 1<3, so no edge? Check condition: For 1 and 3, 1<3 and pos1=3 < pos3=4 => no inversion, so no edge. So {1,3} is independent? But check if edge (1,3) exists: Not in list, so okay. So {1,3} is independent. Also {2,4}? 2<4, pos2=1<pos4=2? Actually pos4=2? Wait positions: a=[2,4,1,3] => pos[2]=1, pos[4]=2, pos[1]=3, pos[3]=4. So {2,4}: 2<4 and pos2=1 < pos4=2, no edge, but is there edge (2,4)? Inversions: 2<4, and pos2<pos4, so no. So {2,4} independent. {1,2}? edge. {1,4}? edge. {3,4}? edge. So max size maybe 2. Could we have {1,2,3}? no because 2-1 edge. {1,3,4}? 4-3 edge. {2,3,4}? 4-3 edge. So max 2. LIS: Increasing subsequences: [2,4]? but then next? Actually [2,4] length2, [2,3] length2 (positions 1 and 4), [1,3] length2, [2]? [4]? So LIS=2. Good.

    Now, what about [5,1,4,2,3]? Let's compute LIS: increasing subsequences: maybe [1,2,3] length3, or [1,4]? Actually [1,2,3] from positions 2,4,5 => length3. So answer would be 3. Now check graph edges (inversions): all pairs where larger before smaller. Inversions: (5,1),(5,4),(5,2),(5,3), (4,2),(4,3), (2,? ) Actually (2,3) not inversion because 2<3 and pos2=4<pos3=5? 2 before 3? Yes pos2=4, pos3=5, 2<3, so no. (1,?) none. So edges: 5 connected to all others; 4 connected to 2 and 3; maybe 2 connected to? 2 and 3 no edge; 1 connected to? only to 5? Actually (1,4)? 1<4 and pos1=2? Wait pos1=2, pos4=3? Actually values: 1 at position2, 4 at position3? pos[1]=2, pos[4]=3, so 1<4 and pos1<pos4, so no. So independent sets: can we find set of size 3? Need three vertices pairwise no edges. Candidates: maybe {1,2,3}? Check 1-2: 1<2, pos1=2, pos2=4 => no edge; 1-3: 1<3, pos1=2, pos3=5 => no edge; 2-3: 2<3, pos2=4, pos3=5 => no edge. So {1,2,3} is independent! That's size 3, matches LIS. Good.

    So all checks out.

    Thus answer is LIS.

    Now, note: There might be alternative interpretations: Some might think that the graph is built on the fly and that after bubble sort, the graph may have edges that are not exactly inversions because edges are added during swaps, and swaps happen between adjacent elements, but what about the case where the same pair gets swapped multiple times? Let's see if it's possible. Consider a scenario: values 5, 1, 2. Initially [5,1,2]. Swap 5 and 1: edge (5,1), becomes [1,5,2]. Next swap 5 and 2: edge (5,2), becomes [1,2,5]. So (5,1) and (5,2) edges. No multiple swaps of same pair. Could a pair be swapped, then later become adjacent again in opposite order? For them to become adjacent again, after swapping they are in correct order (small left, large right). For them to be swapped again, they'd need to be out of order again, i.e., large left of small. Since larger moves right only, it's now to the right of the smaller. To be left again, the larger would have to move left, which can't happen. So no.

    Thus it's safe.

    So final solution: compute LIS length.

    But wait: Could there be any scenario where an edge is added between two numbers that are not an inversion in the initial permutation because the array changes? For instance, consider initial [2,3,1]. Inversions: (2,1) and (3,1). Edges we got: (3,1) and (2,1). That's all. But is (2,3) an inversion? No. So no extra edges.

    Thus all edges are exactly the inversions.

    Thus answer is LIS.

    Now, we should implement accordingly. However, be careful: The graph's vertices are numbers 1..n. The independent set is a set of vertices. So size is number of vertices. LIS length counts values in increasing subsequence. So yes.

    Now, we must consider if there is any nuance about the fact that the graph is constructed during bubble sort, which may produce multiple passes, and edges added might not correspond directly to inversions if we consider the final permutation? But we've already shown equivalence.

    Let's prove: Let inv = set of pairs (x,y) with x>y and pos0(x) < pos0(y), where pos0 is initial position. For any such pair, during bubble sort, there will be a time when x and y are adjacent and swapped. So edge added. Conversely, if edge added between x and y, then at the time of addition, we had x > y and they were adjacent with x left of y. At that moment, their positions are adjacent. Could it be that originally they were not inverted? Suppose initially pos0(x) > pos0(y) (so they were in correct order initially). Then to have x left of y at some later time, x must have moved left or y moved right. But larger x cannot move left; smaller y can move right? Could y move right enough to be to the right of x? For y to move right, it must be larger than some neighbor to its right. y is smaller than x, but could be larger than some other values. Could it overtake x? They start with x right of y (pos0(x) > pos0(y)). For y to become right of x, y would have to move right past x. For that to happen, at some point y and x must be adjacent with y left of x and y > x? But y < x, so that swap never occurs. So they cannot cross. Hence if at some moment x is left of y and x>y, then initially x must have been left of y as well? Actually consider: Initially, maybe x was left of y? If initially x left of y and x>y, then that's an inversion. If initially x right of y, they can't cross, so x cannot become left of y. So any edge added corresponds to an inversion in the initial permutation. So indeed edges = inversions.

    Thus our solution stands.

    Now, the problem might be from Codeforces? Possibly "Bubble Sort Graph" problem. I recall a Codeforces problem: "Bubble Sort Graph" or "Iahub and Bubble Sort"? Actually I recall a problem named "Bubble Sort Graph" from Codeforces Round #198 (Div. 2) problem D? Possibly. The solution indeed is LIS. Yes, I think there is a known problem: "Bubble Sort Graph" which asks for size of maximum independent set after building graph as described. And the answer is LIS. So we are correct.

    Now, implement.

    Complexities: O(n log n) time, O(n) memory (dp array). n up to 1e5, fine.

    Now, one might ask: Is the LIS in terms of values of the permutation? Yes.

    Edge case: n=1? But constraint says n>=2, but if n=1, it's trivial but not needed.

    Thus solution: read n, vector a(n); for i=0..n-1: cin >> a[i]; compute LIS:

    vector dp; for (int x : a) { auto it = lower_bound(dp.begin(), dp.end(), x); if (it == dp.end()) dp.push_back(x); else *it = x; } cout << dp.size() << endl;

    That's it.

    Double-check: For strictly increasing subsequence, we used lower_bound (first element >= x). But is it correct? Standard algorithm for longest strictly increasing subsequence (LIS) using patience sorting: For each x, find the leftmost dp[i] >= x (using binary search), replace it. The length of dp at end is LIS length. That's correct for strict increase. For non-decreasing, we use upper_bound. So here we need strict increase because values are distinct. So lower_bound is fine.

    Now, test with [3,1,2]: dp after: [3]; then 1 replaces 3 => [1]; then 2 lower_bound >=2 => end => push => [1,2]; size 2. Good.

    Test with [1,2,3]: dp: [1]; 2 push => [1,2]; 3 push => [1,2,3]; size 3.

    Test with [3,2,1]: dp: [3]; 2 replaces? lower_bound >=2? dp[0]=3>=2, so dp becomes [2]; 1 replaces? lower_bound >=1 -> dp[0]=2>=1 => dp becomes [1]; size 1. Good.

    Thus correct.

    Now, ensure we use fast I/O because n up to 1e5, but cin/cout with sync_with_stdio(false) fine.

    Now, final answer: We'll output dp.size().

    But is there any possibility that maximum independent set could be larger than LIS due to vertices that are not in increasing subsequence but still independent? As argued, any independent set must be increasing. So no.

    Thus final solution.

    Let's also consider if we need to consider the possibility of multiple edges? But independent set definition: set of vertices with no edges between any two. Even if multiple edges (parallel), it's still an edge. But graph is simple.

    Thus done.

    Now, provide explanation and code.

    But before finalizing, double-check the pseudocode: "build a graph G with n vertices and 0 edges" Then repeat-until swapped false. It says "add an undirected edge in G between a[i] and a[i+1]" and then swap. So yes.

    Now, note: The vertices are numbers 1..n, not indices. So it's consistent.

    Thus answer is LIS.

    Now, we should consider if there is any possibility that the graph edges are not exactly all inversions due to the fact that bubble sort may not swap all inversions because the algorithm might terminate early? But bubble sort continues until no swaps, which means until array is sorted. It will perform all necessary swaps to eliminate all inversions. The total number of swaps in bubble sort equals the number of inversions. So each inversion corresponds to a swap when the two elements become adjacent.

    But is it possible that two inversions are resolved by a single swap? No, each swap resolves exactly one inversion? Actually each swap corrects the order of the two swapped elements but may affect other inversions. However, the number of swaps equals number of inversions, and each swap corresponds to a specific pair of elements that are inverted relative to each other. In bubble sort, each time you swap a pair, you are fixing the inversion between those two specific elements. And that pair is indeed inverted at that moment. And they were inverted initially. So each inversion is swapped exactly once. So edges added = inversions.

    Thus final solution.

    Now, code.

    But maybe there is a twist: The problem might ask for maximum independent set of graph G after running bubble sort. But we derived that graph G is exactly the inversion graph. However, in an inversion graph, maximum independent set equals LIS. But is it possible that the graph constructed by bubble sort is not exactly the inversion graph but rather a subgraph? Because each inversion leads to an edge, but are there any extra edges? Could there be edges added between elements that are not initially inverted but become inverted later? As argued, no. So it's exactly the inversion graph.

    Now, confirm using a more rigorous approach: Define initial permutation p of {1..n}. Bubble sort algorithm: For each pass i from 1 to n-1, we traverse j=1..n-1 and compare p[j] and p[j+1]. If p[j] > p[j+1], swap them and add edge between p[j] (the larger) and p[j+1] (the smaller). After each swap, the two elements are in increasing order locally. The process repeats until no swaps. It is known that bubble sort performs exactly the set of swaps that are the "adjacent swaps" needed to sort, and the set of pairs that ever get swapped is precisely the set of inversions in the original permutation. This is a standard result. So fine.

    Thus answer.

    Now, we can present the solution.

    But wait: Could there be a scenario where two elements are swapped, but they are not inverted in the initial permutation? Let's attempt to artificially construct: start with [1,3,2]. This is not sorted. Inversions: (3,2). The only swap occurs between 3 and 2. That's an inversion. So fine.

    What about [2,1,3]? Inversions: (2,1). Swap between 2 and 1. That's inversion.

    Consider [3,1,2] we saw.

    Consider [4,2,3,1]. Inversions: (4,2),(4,3),(4,1),(2,1),(3,1). The swaps: (4,2),(4,3),(4,1),(3,1),(2,1). All inversions.

    What about a longer case: [2,4,1,5,3]. Let's compute inversions: (2,1) because 2>1 and pos2=1<pos1=3? Actually pos2=1, pos1=3 => inversion; (4,1), (4,3), (5,3). Also (2,? ) 2<3? pos2=1, pos3=5 => 2<3 and pos2<pos3, so not inversion; (4,? ) 4<5? pos4=2, pos5=4? Actually pos5? Wait values: a=[2,4,1,5,3]. So positions: 1 at index3, 2 at 1, 3 at5,4 at2,5 at4. So inversion pairs: (2,1): 2>1 pos2<pos1 -> yes; (4,1): yes; (4,3): 4>3 pos4=2<pos3=5? Yes; (5,3): yes; Also (2,?) (2,? ) none else; (4,? ) maybe (4,? )? (4,5)? 4<5 pos4=2<pos5=4, no; (5,? ) (5,1)? 5>1 pos5=4 > pos1=3? Actually pos5=4, pos1=3, so 5>1 and pos5 > pos1? That means 5 appears after 1, so not inversion (since inversion requires larger before smaller). So no; (2,3)? 2<3 pos2=1<pos3=5, no; (2,4)? 2<4 pos2=1<pos4=2, no; (1,3)? 1<3 pos1=3<pos3=5, no; So total 4 inversions.

    Now simulate bubble sort passes quickly to see if all these edges appear:

    Initial: [2,4,1,5,3] Pass1: i=1: 2<4 no swap. i=2: 4>1 swap -> edge (4,1) => [2,1,4,5,3] i=3: 4<5 no swap? Wait after swap, array now [2,1,4,5,3] and i=3 compares a[3]=4 and a[4]=5 => 4<5 no swap. i=4: 5>3 swap -> edge (5,3) => [2,1,4,3,5] (after i=4) swapped true. Pass2: i=1: 2>1 swap -> edge (2,1) => [1,2,4,3,5] i=2: 2<4 no swap. i=3: 4>3 swap -> edge (4,3) => [1,2,3,4,5] i=4: 4<5 no swap. swapped true. Pass3: no swaps. Edges: (4,1), (5,3), (2,1), (4,3). That's exactly the four inversions. So again matches.

    Thus confident.

    Now, the solution is to compute LIS. However, note: Because the graph is defined on values, the LIS is computed on the permutation as given (the sequence a). But we might also think of it as the longest decreasing subsequence of the inverse permutation? But same.

    So implement.

    Now, there might be a catch: The graph built is undirected. The maximum independent set in a permutation graph can also be computed via LIS. But is it always true that the maximum independent set size equals LIS? Yes, because the permutation graph is perfect and its complement is also comparability, but the independent set corresponds to a chain in the permutation poset? Actually we can view each vertex as a point (value, position). Two vertices are adjacent if the points are crossing (i.e., one is above-left of the other? Let's define: For value v, we have (v, pos[v]). Two vertices u<v are adjacent iff pos[u] > pos[v], which means the point for u is to the right? Actually if we plot with x-coordinate = value, y-coordinate = position, then edge if the segments... But anyway, independent set means no crossing, which implies that the points are all comparable in the order: either all values increase with positions, i.e., they form a monotonic sequence. So it's exactly increasing subsequence.

    Thus correct.

    Now, we should provide a solution.

    But before finalizing, I'll consider if there is any possibility that the maximum independent set is not simply LIS because the graph might contain additional edges beyond inversions. Let's consider a scenario where the same pair might be swapped twice? Could that happen? To examine, consider three elements: a,b,c with values such that? Suppose we have values 2,1,3? Already done. What about 3,2,1? All pairs swapped, each once. Could 2 and 3 be swapped twice? In bubble sort for 3,2,1: first pass: swap 3 and 2, then later swap 3 and 1? But 2 and 3 after first swap become [2,3,1]. Then in second pass, we compare 2 and 3: they are in correct order, so no swap. So 2 and 3 are never swapped again. So no.

    Consider 4,1,3,2? Already done. No double swaps.

    Thus safe.

    Now, maybe there is a nuance: The graph adds edges between a[i] and a[i+1] at the moment of swap. But after swapping, the values move. Could an edge be added between two values that were originally not inverted but become inverted because the relative order of values changes due to other swaps? For instance, consider initial permutation: [2,3,1]. Initially, 2 and 3 are not inverted. Could they become inverted later? 2<3, they are in order. After swaps: first swap 3 and 1 -> [2,1,3]. Now positions: 2 at pos1, 1 at pos2, 3 at pos3. 2 and 3: 2<3 and pos2=1<pos3=3, still in order. No inversion. Later swap 2 and 1 -> [1,2,3]. Still fine. So no.

    Consider [3,1,4,2]. Initially, 3 and 4: 3<4, pos3=1, pos4=3, order okay. After some swaps: pass1: i=1: 3>1 swap -> edge(3,1), becomes [1,3,4,2]; i=2: 3<4; i=3:4>2 swap -> edge(4,2), becomes [1,3,2,4]. Now check 3 and 4: values 3 and 4: 3<4, pos3=2? Actually now positions: 1 at pos1, 3 at pos2, 2 at pos3, 4 at pos4. So pos3=2, pos4=4, still pos3<pos4, so no inversion. Later pass2: i=2: compare a[2]=3 and a[3]=2: 3>2 swap -> edge(3,2), becomes [1,2,3,4]. Then i=3: 3<4 no swap. So still 3 and 4 not swapped.

    Thus no extra edges.

    Thus it's safe.

    Now, we implement.

    One more thought: Could the graph be considered as the "swap graph" of bubble sort? Yes.

    Thus final answer: LIS.

    Now, complexity: O(n log n) time, O(n) space.

    We'll write code accordingly.

    Now, provide final answer with explanation.

    But wait, there is a known trick: For permutation graphs, the maximum independent set can be found by longest increasing subsequence. But we need to be careful about the fact that the vertices are numbers, not indices. However, the LIS is on the given permutation. That's fine.

    We can also compute by sorting vertices by value and then finding longest increasing sequence of positions. That's equivalent to LIS on the permutation. Since we already have the permutation as a sequence of values, the LIS directly gives the answer.

    Thus final solution.

    Now, code:

    #include #include #include

    using namespace std;

    int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector a(n); for (int i=0; i<n; ++i) cin >> a[i]; vector dp; for (int x : a) { auto it = lower_bound(dp.begin(), dp.end(), x); if (it == dp.end()) dp.push_back(x); else *it = x; } cout << dp.size() << endl; return 0; }

    Check with sample: Input 3 3 1 2 => output 2. Good.

    Now, consider maybe n up to 10^5, dp size at most n, binary search O(log n). So fine.

    Thus answer.

    Now, provide solution with explanation.

    But wait, is there any need to handle large input? Use fast I/O.

    Thus final. The graph constructed by Bubble Sort connects two numbers if and only if they form an inversion in the original permutation.
    Thus the graph is exactly the inversion (permutation) graph of the permutation.

    In such a graph, a set of vertices is independent iff, when sorted by their numeric values, their positions in the permutation are increasing.
    This is precisely the definition of an increasing subsequence of the given permutation.
    Hence the size of a maximum independent set equals the length of the longest increasing subsequence (LIS).

    The LIS can be computed in (O(n \log n)) using a standard algorithm with binary search.

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
    
        vector<int> dp;                // dp[i] = smallest possible last element of an IS of length i+1
        for (int x : a) {
            auto it = lower_bound(dp.begin(), dp.end(), x);
            if (it == dp.end())
                dp.push_back(x);
            else
                *it = x;
        }
        cout << dp.size() << '\n';
    
        return 0;
    }