تم إعطاؤك مصفوفة من عصي سحرية ، حيث العصا لها طول a_i. نسمي مصفوفة العصي جيدة، إذا كان هناك ثلاثي (1 \le i < j < k \le |b|)، بحيث يوجد مثلث غير متناهي الأضلاع بأضلاع b_i، b_j و b_k.
يُطلب منك التعامل مع استفسارات من نوعين:
— العصا السحرية في الموضع قد غيرت طولها إلى ؛
— اطبع الحد الأقصى لعدد الأجزاء المتجاورة غير الفارغة التي يمكن تقسيم إليها بحيث تكون كل جزء جيدة. يرجى ملاحظة أنه يجب أن ينتمي كل عنصر إلى جزء جيد. إذا لم يكن بالإمكان تقسيم الجزء إلى أجزاء متجاورة غير فارغة، فإن الإجابة هي 0.
السطر الأول من المدخلات يحتوي على عددين صحيحين و (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).
لكل استفسار من النوع ، اطبع سطرًا واحدًا يحتوي على عدد صحيح واحد — الحد الأقصى لعدد الأجزاء المتجاورة غير الفارغة التي يمكن تقسيم الجزء إليها بحيث تكون كل جزء جيدة. إذا لم يكن بالإمكان تقسيم الجزء إلى أجزاء متجاورة غير فارغة، اطبع .
Example 1
المصفوفة الأولية هي 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).
( نقاط) n,q \le 1000، لا توجد استفسارات تحديث؛
( نقاط) n,q \le 1000؛
( نقاط) لا توجد استفسارات تحديث؛
( نقاط) a_i \le 100، لكل في الاستفسارات أقل من أو يساوي ؛
( نقاط) n \le 10^5؛
( نقاط) لا توجد قيود إضافية.