Limits 1.5s, 512 MB

চলো এবার আমরা বেশি বর্ণনা না করে সরাসরি প্রবলেম নিয়ে আলোচনা করি: D

তোমাকে একটা N সংখ্যক পূর্ণসংখ্যার অ্যারে A দেয়া আছে। অ্যারেটার উপাদানগুলো হল A1, A2, A3 ... AN। তোমাকে Q সংখ্যক কুয়েরিও দেয়া হয়েছে এই অ্যারে A এর উপর প্রয়োগ করার জন্য। প্রতিটা কুয়েরিতে তোমাকে তিনটা পূর্ণসংখ্যা L, R, X দেয়া হবে, যেখানে [L, R] অ্যারে A এর একটা সাব-সেগমেন্ট নির্দেশ করে যা L থেকে শুরু হয় এবং R এ গিয়ে শেষ হয়। তোমাকে বের করতে হবে A অ্যারের [L, R] সাব-সেগমেন্টের সবগুলো ভ্যালু X এর সমান করতে সর্বনিম্ন কতগুলো অপারেশন লাগবে, যেন AL = AL+1 = AL+2 = ... = AR = X হয়।

দুই ধরণের অপারেশন আছে। তুমি এই দুটি অপারেশনের যেকোনোটা যেকোনো সংখ্যকবার প্রয়োগ করতে পারো।

দুই ধরণের অপারেশন নিচে বর্ণনা করা হল-

অপারেশন ১ঃ তুমি অ্যারের যেকোনো একটা ইনডেক্স i (1 ≤ i ≤ N) বাছাই করে Ai = Ai + 1 করতে পারো।

অপারেশন ২ঃ তুমি অ্যারের যেকোনো একটা ইনডেক্স i (1 ≤ i ≤ N) বাছাই করে Ai = Ai - 1 করতে পারো।

নোটঃ প্রতিটা কুয়েরি স্বাধীন।

Input

প্রথম লাইনে একটি পূর্ণসংখ্যা T(1 ≤ T ≤ 5) দেয়া থাকবে, যা টেষ্টকেসের সংখ্যা।
প্রতিটা টেষ্টকেস একটি পূর্ণসংখ্যা N(1 ≤ N ≤ 105) দিয়ে শুরু হবে, যা অ্যারের উপাদান সংখ্যা।
পরবর্তি লাইনে অ্যারের উপাদানগুলো A1, A2, ..., AN (-109 ≤ Ai ≤ 109) দেয়া থাকবে।
পরবর্তি লাইনে একটি পূর্ণসংখ্যা Q(1 ≤ Q ≤ 105) দেয়া থাকবে, যা কুয়েরি সংখ্যা।
পরবর্তি লাইনে তিনটি পূর্ণসংখ্যা L, R(1 ≤ L ≤ R ≤ N) এবং X(-1012 ≤ X ≤ 1012) দেয়া থাকবে।

সাবটাস্ক
সাবটাস্ক #1(10 পয়েন্ট)
1 ≤ N, Q ≤ 103.
সাবটাস্ক #2(30 পয়েন্ট)
1 ≤ N, Q ≤ 105.
A অ্যারেতে সর্বোচ্চ 10 টা আলাদা ভ্যালু থাকবে।
সাবটাস্ক #3(60 পয়েন্ট)
অরিজিনাল কনস্ট্রেন্ট।

Output

প্রতিটা টেষ্টকেসের জন্য আলাদা লাইনে কেসের সংখ্যা প্রিন্ট করো।
তারপর প্রতিটা কুয়েরির জন্য A অ্যারের [L, R] সাব-সেগমেন্টের সবগুলো ভ্যালু X এর সমান করার জন্য সর্বনিম্ন যতগুলো অপারপশন লাগবে তা প্রিন্ট করো।

Sample

InputOutput
1
3
4 5 6
2
1 3 6
1 3 4
Case 1:
3
3

১ম কুয়েরিতে, তোমাকে "অপারেশন ১" ১ম ইনডেক্সে দুইবার এবং ২য় ইনডেক্সে একবার প্রয়োগ করতে হবে। তাই উত্তর 3 হবে।

২য় কুয়েরিতে, তোমাকে "অপারেশন ২" ২য় ইনডেক্সে একবার এবং ৩য় ইনডেক্সে দুইবার প্রয়োগ করতে হবে। তাই উত্তর 3 হবে।

Submit

Login to submit.

Statistics

48% Solution Ratio
prodip_bsmrstuEarliest, Aug '20
EgorKulikovFastest, 0.3s
user.536969Lightest, 9.2 MB
MursaleenShortest, 1682B
Toph uses cookies. By continuing you agree to our Cookie Policy.