Mike is the president of country What-The-Fatherland. There are *n* bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to *n* from left to right. *i*-th bear is exactly *a*<sub class="lower-index">*i*</sub> feet high. 

A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strength of a group is the minimum height of the bear in that group.

Mike is a curious to know for each *x* such that 1 ≤ *x* ≤ *n* the maximum strength among all groups of size *x*.
The first line of input contains integer *n* (1 ≤ *n* ≤ 2 × 10<sup class="upper-index">5</sup>), the number of bears.

The second line contains *n* integers separated by space, *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>), heights of bears.
class dsu():
    """Data structures and algorithms for disjoint set union problems.
    
    Given an undirected graph, it processes the following queries in O(α(n)) time (amortized).

    >   Edge addition
    
    >   Deciding whether given two vertices are in the same connected component

    Each connected component internally has a representative vertex.

    When two connected components are merged by edge addition, one of the two representatives of these connected components becomes the representative of the new connected component.
    """


    __slots__ = ["_n", "parent_or_size"]


    def __init__(self, n):
        """
        It creates an undirected graph with n vertices and 0 edges.
        
        Constraints
        -----------

        >   0 ≤ n ≤ 10 ** 8

        Complexity
        ----------

        >   O(n)
        """
        self._n = n
        self.parent_or_size = [-1] * n
    
    
    def merge(self, a, b):
        """
        It adds an edge (a, b).

        If the vertices a and b were in the same connected component, it returns the representative of this connected component. Otherwise, it returns the representative of the new connected component.
       
        Constraints
        -----------

        >   0 ≤ a < n 

        >   0 ≤ b < n
        
        Complexity
        ----------

        >   O(α(n)) amortized
        """
        # assert 0 <= a < self._n
        # assert 0 <= b < self._n
        x = self.leader(a)
        y = self.leader(b)
        if x == y:
            return x
        else:
            if self.parent_or_size[y] < self.parent_or_size[x]:
                x, y = y, x
            self.parent_or_size[x] += self.parent_or_size[y]
            self.parent_or_size[y] = x


    def same(self, a, b):
        """
        It returns whether the vertices a and b are in the same connected component.

        Constraints
        -----------

        >   0 ≤ a < n

        >   0 ≤ b < n

        Complexity
        ----------

        >   O(α(n)) amortized
        """
        # assert 0 <= a < self._n
        # assert 0 <= b < self._n
        return self.leader(a) == self.leader(b)


    def leader(self, a):
        """
        It returns the representative of the connected component that contains the vertex a.

        Constraints
        -----------

        >   0 ≤ a < n

        Complexity
        ----------

        >   O(α(n)) amortized
        """
        # assert 0 <= a < self._n
        path = []
        while self.parent_or_size[a] >= 0:
            path.append(a)
            a = self.parent_or_size[a]
        for child in path:
            self.parent_or_size[child] = a
        return a

    
    def size(self, a):
        """
        It returns the size of the connected component that contains the vertex aa.

        Constraints
        -----------

        >   0 ≤ a < n
        
        Complexity
        ----------

        >   O(α(n)) amortized
        """
        # assert 0 <= a < self._n
        return -self.parent_or_size[self.leader(a)]


    def groups(self):
        """
        It divides the graph into connected components and returns the list of them.

        More precisely, it returns the list of the "list of the vertices in a connected component". Both of the orders of the connected components and the vertices are undefined.

        Complexity
        ----------

        >   O(n)
        """
        anc2mem = dict()
        for i in range(self._n):
            anc = self.leader(i)
            if anc in anc2mem:
                anc2mem[anc].append(i)
            else:
                anc2mem[anc] = [i]
        return list(anc2mem.values())


def main():
    import sys
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    ans = []
    g = dsu(N)
    for _ in range(Q):
        t, u, v = map(int, input().split())
        if t:
            ans.append('1' if g.same(u, v) else '0')
        else:
            g.merge(u, v)
    print('\n'.join(ans))

if __name__ == "__main__":
    main()