Irish Whiskey#7989

Irish Whiskey

1 second

128 megabytes

Hard

You are given an array $A$ of $n$ integers (indexed from $1$ ). You need to process two types of queries:

Swap $A_{l}$ A_l and $A_{r}$ A_r.
Determine if the subarray $A_{l}, A_{l + 1}, \dots, A_{r}$ A_l, A_{l+1}, \ldots, A_r is sorted in non-decreasing order.

\InputFileThe first line contains two integers $n$ and $q$ ( $1 \leq n \leq 300000$ 1 \leq n \leq 300\,000, $1 \leq q \leq 200000$ 1 \leq q \leq 200\,000) — the length of the array and the number of queries.

The second line contains $n$ integers $A_{1}, A_{2}, \dots, A_{n}$ A_1, A_2, \ldots, A_n ( $1 \leq A_{i} \leq 1 0^{9}$ 1 \leq A_i \leq 10^9).

Each of the following $q$ lines describes a query. Each line contains three integers: the type of the query $t$ ( $1$ or $2$ ), and two integers $l$ and $r$ ( $1 \leq l \leq r \leq n$ 1 \leq l \leq r \leq n).

If $t = 1$ t = 1, swap $A_{l}$ A_l and $A_{r}$ A_r.

If $t = 2$ t = 2, check whether the subarray $A_{l}, \dots, A_{r}$ A_l, \ldots, A_r is sorted in non-decreasing order.

\OutputFileFor each query of the second type, output a single line containing Ja if the subarray is sorted in non-decreasing order, or Nein otherwise.

Examples

Example 1

Loading

A_{l}

A_{r}

A_{l}, A_{l + 1}, \dots, A_{r}

1 \leq n \leq 300000

1 \leq q \leq 200000

A_{1}, A_{2}, \dots, A_{n}

1 \leq A_{i} \leq 1 0^{9}

1 \leq l \leq r \leq n

t = 1

A_{l}

A_{r}

t = 2

A_{l}, \dots, A_{r}