Hello everyone!

I've been thinking about solution to the following problem for few days and didn't come up with any reasonable idea. Could you help me out?

You're given array of n elements and q queries. Every query is one of two type:

1) Reverse interval [l, r], e.g. for array 1 2 3 4 5 6 and query [2, 5] we end up with 1 5 4 3 2 6.

2) Ask for sum on interval [l, r].

Thanks and have a nice Sunday.