مثلثات جيدة#524

مثلثات جيدة

4 ثوان
256 ميغابايت
Very hard

تم إعطاؤك مصفوفة من عصي سحرية ، حيث العصا لها طول a_i. نسمي مصفوفة العصي جيدة، إذا كان هناك ثلاثي (1 \le i < j < k \le |b|)، بحيث يوجد مثلث غير متناهي الأضلاع بأضلاع b_i، b_j و b_k.

يُطلب منك التعامل مع استفسارات من نوعين:

Input

السطر الأول من المدخلات يحتوي على عددين صحيحين و (1 \le n,q \le 5 \cdot 10^5) — طول مصفوفة العصا السحرية وعدد الاستفسارات.

السطر الثاني من المدخلات يحتوي على عدد صحيح a_i (1 \le a_i \le 10^6) — أطوال العصا السحرية في المصفوفة .

كل من الأسطر التالية تحتوي على استفسار واحد من أحد الأنواع التالية:

  • (1 \le i \le n, 1 \le x \le 10^6)؛

  • (1 \le l \le r \le n).

Output

لكل استفسار من النوع ، اطبع سطرًا واحدًا يحتوي على عدد صحيح واحد — الحد الأقصى لعدد الأجزاء المتجاورة غير الفارغة التي يمكن تقسيم الجزء إليها بحيث تكون كل جزء جيدة. إذا لم يكن بالإمكان تقسيم الجزء إلى أجزاء متجاورة غير فارغة، اطبع .

Examples

Example 1

Loading
Loading

Note

المصفوفة الأولية هي a = [1, 3, 5, 4, 7, 5, 4, 3, 9, 8].

استفسار "2 1 10": يمكننا تقسيم المصفوفة الكاملة إلى أجزاء جيدة: [1, 3, 5, 4]، [7, 5, 4]، [3, 9, 8].

  • [1, 3, 5, 4] جيدة: العصا بطول ، ، تشكل مثلثًا (3 + 4 > 5).

  • [7, 5, 4] جيدة: العصا بطول ، ، تشكل مثلثًا (4 + 5 > 7).

  • [3, 9, 8] جيدة: العصا بطول ، ، تشكل مثلثًا (3 + 8 > 9).

استفسار "1 3 3": تصبح المصفوفة a = [1, 3, 3, 4, 7, 5, 4, 3, 9, 8].

استفسار "2 1 10": يمكننا تقسيم المصفوفة الكاملة إلى أجزاء جيدة: [1, 3, 3]، [4, 7, 5]، [4, 3, 9, 8].

  • [1, 3, 3] جيدة: العصا بطول ، ، تشكل مثلثًا (1 + 3 > 3).

  • [4, 7, 5] جيدة: العصا بطول ، ، تشكل مثلثًا (4 + 5 > 7).

  • [4, 3, 9, 8] جيدة: العصا بطول ، ، تشكل مثلثًا (4 + 8 > 9).

استفسار "2 1 7": الجزء الفرعي هو [1, 3, 3, 4, 7, 5, 4]. يمكننا تقسيمه إلى أجزاء جيدة: [1, 3, 3] و [4, 7, 5, 4].

  • [1, 3, 3] جيدة: 1 + 3 > 3.

  • [4, 7, 5, 4] جيدة: العصا بطول ، ، تشكل مثلثًا (4 + 4 > 5).

استفسار "2 3 8": الجزء الفرعي هو [3, 4, 7, 5, 4, 3]. يمكننا تقسيمه إلى جزء جيد: [3, 4, 7, 5, 4, 3].

  • [3, 4, 7, 5, 4, 3] جيدة: العصا بطول ، ، تشكل مثلثًا (3 + 4 > 5).

Scoring

  1. ( نقاط) n,q \le 1000، لا توجد استفسارات تحديث؛

  2. ( نقاط) n,q \le 1000؛

  3. ( نقاط) لا توجد استفسارات تحديث؛

  4. ( نقاط) a_i \le 100، لكل في الاستفسارات أقل من أو يساوي ؛

  5. ( نقاط) n \le 10^5؛

  6. ( نقاط) لا توجد قيود إضافية.