لعبة الفواكه لعبة تُدمج فيها فواكه من أنواع مختلفة لإنشاء أنواع أكبر من الفواكه. يمكن تمثيل اللوحة بمتتالية $X[0],X[1],\ldots,X[K-1]$. كل عدد هو معرّف نوع الفاكهة، والمعرّف الأكبر يعني فاكهة أكبر حجمًا.

يمكن للاعب تنفيذ عملية دمج تجمع فاكهتين متجاورتين من النوع نفسه في فاكهة أكبر. تُعرَّف العملية كما يلي.

الدمج: على اللوحة $X[0],X[1],\ldots,X[K-1]$، اختر عددًا صحيحًا $0\le i\le K-2$. إذا تحقق $X[i]=X[i+1]$، فاستبدل اللوحة بـ $X[0],\ldots,X[i-1],X[i]+1,X[i+2],\ldots,X[K-1]$.

عند إعطاء اللوحة الابتدائية، يكون هدف اللاعب إنشاء فاكهة كبيرة باستخدام صفر أو أكثر من عمليات الدمج.

مثلًا، على اللوحة $X=[2,1,1,3,2]$، بما أن $X[1]=X[2]$، فإن اختيار $i=1$ والدمج يغيّر اللوحة إلى $X=[2,2,3,2]$. وبما أن $X[0]=X[1]$، فإن اختيار $i=0$ والدمج يغيّرها إلى $X=[3,3,2]$. وأخيرًا، بما أن $X[0]=X[1]$، فإن اختيار $i=0$ والدمج يغيّرها إلى $X=[4,2]$. بذلك يمكن إنشاء فاكهة معرّفها $4$، وهو أكبر معرّف فاكهة يمكن الحصول عليه.

تُعطى متتالية $A$ طولها $N$. قد تتغير عناصرها، وتتراكم هذه التغييرات. كلما أُعطي زوج مرتب من الأعداد الصحيحة $(l,r)$ يحقق $0\le l\le r\le N-1$، عليك إيجاد أكبر معرّف فاكهة يمكن الحصول عليه من اللوحة $A[l],\ldots,A[r]$. يوجد $Q$ أحداث إجمالًا، كل منها تغيير عنصر أو إعطاء زوج.

تفاصيل التنفيذ

عليك تنفيذ الدوال التالية.

void prepare_game(std::vector<int> A)

• $A$: مصفوفة أعداد صحيحة حجمها $N$.
• تُستدعى هذه الدالة مرة واحدة فقط، وقبل جميع الدوال الأخرى.
• يمكن تنفيذ أي معالجة مسبقة أو تهيئة متغيرات عامة لازمة للاستدعاءات اللاحقة في هذه الدالة.

int play_game(int l, int r)

• يجب أن تعيد هذه الدالة أكبر معرّف فاكهة يمكن الحصول عليه من اللوحة $A[l],\ldots,A[r]$.
• تُستدعى هذه الدالة مرة واحدة على الأقل.

void update_game(int p, int v)

• غيّر قيمة $A[p]$ إلى $v$.

إجمالي عدد استدعاءات play_game وupdate_game هو $Q$.

يُمنع تنفيذ دوال إدخال/إخراج في أي موضع من الشيفرة المصدرية المقدمة.

ملاحظة

$A[i],\ldots,A[j]$ هي المتتالية ذات الطول $j-i+1$ المكوّنة من عناصر $A$ من العنصر $i$ إلى العنصر $j$. مثلًا، عندما تكون $A=[3,5,7,2,9]$، تكون $A[1],\ldots,A[3]$ هي $[5,7,2]$، وتكون $A[4],\ldots,A[4]$ هي $[9]$.

القيود

• $1\le N,Q\le100\,000$
• $1\le A[i]\le10$ ($0\le i\le N-1$).
• لكل استدعاء لـ play_game: $0\le l\le r\le N-1$.
• لكل استدعاء لـ update_game: $0\le p\le N-1$، $1\le v\le10$.

المهام الفرعية

1 (5 نقطة)

• $N\le10$.
• $Q\le10$.

2 (6 نقطة)

• $N\le600$.
• $Q\le600$.

3 (8 نقطة)

• $N\le4\,000$.
• $Q\le4\,000$.
• $A[i]\le2$ ($0\le i\le N-1$).
• لكل استدعاء لـ update_game: $v\le2$.

4 (15 نقطة)

• $N\le4\,000$.
• $Q\le4\,000$.

5 (12 نقطة)

• $A[i]\le2$ ($0\le i\le N-1$).
• لكل استدعاء لـ update_game: $v\le2$.

6 (14 نقطة)

• لا تُستدعى update_game.

7 (40 نقطة)

• لا توجد قيود إضافية.

أمثلة

أمثلة 1

لننظر إلى الحالة $N=5$, $A=[2,1,1,3,4]$.

يستدعي المقيّم الدوال التالية بالترتيب.

prepare_game([2, 1, 1, 3, 4])
play_game(0, 4) = 5
update_game(2, 3)
play_game(2, 4) = 5
update_game(1, 2)
play_game(0, 2) = 4

أمثلة 2

لننظر إلى الحالة $N=7$, $A=[1,1,1,1,2,2,2]$.

يستدعي المقيّم الدوال التالية بالترتيب.

prepare_game([1, 1, 1, 1, 2, 2, 2])
play_game(0, 6) = 4
play_game(2, 4) = 3
update_game(6, 4)
play_game(4, 6) = 4
play_game(0, 6) = 5

المقيّم النموذجي

يقرأ المقيّم النموذجي الإدخال بالصيغة التالية.

• السطر 1: $N$.
• السطر 2: $A[0]\ A[1]\ \cdots\ A[N-1]$.
• السطر 3: $Q$.
• السطر $3+i$ ($1\le i\le Q$): 1 l r لاستدعاء play_game، أو 2 p v لاستدعاء update_game.

يطبع المقيّم النموذجي ما يلي.

• السطر $i$: القيمة التي أعادها الاستدعاء رقم $i$ للدالة play_game.

لاحظ أن المقيّم النموذجي قد يختلف عن المقيّم المستخدم في التقييم الفعلي.