# [CHG::OJ] Free Fire Contest 2023 - 02

:::info
:bulb: Educational contest written by [sweetestlove](http://chuyenhagiang.ntucoder.net/Coder/Details/sweetestlove)

:timer_clock: Thời gian làm bài: 180 phút

:::

## Bài 1: Biết ông Liêm không?

:::warning
Giới hạn thời gian: 2 giây / Giới hạn bộ nhớ: 256 MB
:::

Hôm nay ông Liêm đi dự sinh nhật của bà Sắc, ông Liêm dự tính tặng bà Sắc một dãy số nguyên dương $a$ có $n$ phần tử.

Dãy số của ông Liêm dự tính tặng là hàng gia truyền có từ $1000$ năm trước nên không tránh khỏi tình trạng bị mối mọt cắn mất vài con số. Ông Liêm biết bà Sắc không thích dãy số có $2$ phần tử liên tiếp nhau chênh lệch quá lớn. Ông Liêm không có nhiều thời gian nên phải tìm gấp $1$ số nguyên $k$.

Đặt $m$ là giá trị tuyệt đối lớn nhất giữa $2$ phần tử kế tiếp nhau (nói cách khác, $|a_i−a_{i+1}|$ với mọi $(1≤i≤n−1)$

Ông Liêm nhờ bạn tìm số $k$ sao cho $m$ là nhỏ nhất. Hãy giúp ông Liêm nhé.

### Đầu vào:
Dòng đầu tiên: số nguyên $n$ $(2≤n≤10^5)$ - số phần tử trong dãy số.
Dòng tiếp theo chữa $n$ số nguyên, $a_1,a_2,…,a_n$ $(−1≤a_i≤10^9)$, $a_i=1$ tức là số ấy đang bị mất và cần bạn tìm chúng.

### Đầu ra:
In ra 2 số, $m$ và $k$.

### Ví dụ:

$Input$ $1$:

5
-1 10 -1 12 -1

$Output$ $1$:

`
1 11
`

> *Thay tất cả các số mất thành 11.*

$Input$ $2$:

5
-1 40 35 -1 35

$Output$ $2$:

`
5 35
`

$Input$ $3$:

6
-1 -1 9 -1 3 -1

$Output$ $3$:

`
3 6
`

---

## Bài 2: Câu cá

:::warning
Giới hạn thời gian: 1 giây / Giới hạn bộ nhớ: 256 MB
:::

Khi đang đi câu cá, một thanh niên tên Urashima-Taro đã phát hiện một chú rùa đang bị một nhóm trẻ em hành hạ.
Anh vội chạy đến cứu và thả nó xuống nước.
Vài ngày sau, anh được con rùa đến thăm, con rùa đã nói với Taro rằng, anh đã cứu mạng con vật cưng quý giá của Otohime, con gái của Ryujin, hoàng đế của biển cả.
Để bày tỏ lòng cảm ơn, hoàng đế đã mời anh chàng Urashima-Taro ghé thăm cung điện của Long Thần Ryugu. Tại nơi đây, anh được chào đón nhiệt tình bởi hoàng đế và con gái Otohime.
Taro đã phải lòng cô gái ấy, sau một thời gian chung sống, Urashima-Taro cảm thấy nhớ nhà và muốn trở lại đất liền. Otohime đã đưa cho Urashima-Taro một chiếc hộp nạm ngọc và cảnh báo anh ta tuyệt đối không được mở nó ra.
Khi trở lại đất liền, Taro phát hiện ra rằng trong khi anh ở dưới nước chỉ mới vài ngày thì tại nơi đây đã trải qua rất nhiều năm.
Không còn ai nhận ra mình nữa, Urashima-Taro đã mở chiếc hộp nạm ngọc mà cô gái đưa cho. Thứ bên trong chiếc hộp đã làm cho anh kinh hoàng, trong đó là bài toán thứ 2 của đề hôm nay!!!

Cho một dãy có $n$ phần tử và $m$ truy vấn. Truy vấn thứ $i$ được biểu diễn bằng $l_i, r_i, x_i$.
Với truy vấn thứ $i$ tìm vị trí bất kì $p_i$ $(l_i ≤ p_i ≤ r_i)$ sao cho $a_{p_i} ≠ x_i$.

### Đầu vào:
Dòng đầu tiên chứa hai số nguyên $n, m$ $(1 ≤ n, m ≤ 2·10^5)$ — số lượng phần tử trong a và số lượng truy vấn.
Dòng thứ hai chứa $n$ số nguyên $a_i$ $(1 ≤ a_i ≤ 10^6)$ — các phần tử của mảng $a$.
Mỗi m dòng tiếp theo chứa ba số nguyên $l_i, r_i, x_i$ $(1 ≤ l_i ≤ r_i ≤ n, 1 ≤ x_i ≤ 10^6)$ — các tham số của truy vấn thứ $i$.

### Đầu ra:
In $m$ dòng. Trên dòng thứ $i$ in số nguyên $p_i$ — vị trí của bất kỳ số nào không bằng $x_i$ trong đoạn $[l_i, r_i]$ hoặc giá trị  $- 1$ nếu không có số đó.

### Ví dụ:

$Input$ $1$:

6 4
1 2 1 1 3 5
1 4 1
2 6 2
3 4 1
3 4 2

$Output$ $1$:

`
2
6
-1
4
`

---

## Bài 3: Có cái nịt

:::warning
Đoán đề bài đi
:::