Due to the large input size it is recommended to use an efficient reader.
An array $$$a_1,a_2, \ldots a_n$$$ of $$$n \ge 1$$$ integers is bordered if all of its elements belong to the interval determined by $$$a_1$$$ and $$$a_n$$$.
More exactly, $$$a$$$ is bordered if $$$a_1 \le a_i \le a_n$$$, $$$\forall i \in [1,n]$$$. Therefore, any array of $$$n \le 2$$$ elements is bordered if $$$a_1 \le a_n$$$.
For example, $$$[1]$$$, $$$[1,1]$$$, $$$[3,4,3,4]$$$ and $$$[1,3,2,4]$$$ are bordered arrays, while $$$[\varnothing]$$$, $$$[2,3,1]$$$ and $$$[2,1,4,3]$$$ are not.
For a given array $$$a=[a_1,a_2, \ldots, a_n]$$$, find how many of its subarrays are bordered.
The first line of input contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the number of elements of $$$a$$$. The second line of input contains $$$n$$$ space separated integers, the elements of array $$$a$$$ ($$$1 \le a_i \le 10^9$$$).
Print one integer, the number of bordered subarrays of $$$a$$$.
- Subtask 1 (10 points): $$$1 \le n \le 300$$$;
- Subtask 2 (15 points): $$$1 \le n \le 10^5$$$, $$$1 \le a_i \le 2$$$;
- Subtask 3 (20 points): $$$300 \lt n \le 5000$$$;
- Subtask 4 (30 points): $$$5000 \lt n \le 10^5$$$;
- Subtask 5 (25 points): No further constraints.
5 1 2 4 3 5
11
8 2 1 6 3 6 7 8 5
18
In the first sample, the $$$11$$$ bordered subarrays are $$$[1]$$$, $$$[2]$$$, $$$[4]$$$, $$$[3]$$$, $$$[5]$$$, $$$[1,2]$$$, $$$[2,4]$$$, $$$[3,5]$$$, $$$[1,2,4]$$$, $$$[2,4,3,5]$$$ and $$$[1,2,4,3,5]$$$.
' In the civil court of the Mayan emperor, lived a prophet. And this prophet prophesied that "The difference is made by the man who is motivated in every what he did is no longer valid tomorrow a take from 0 will prove that again the best". Now, unfortunately, he neither knew nor was he aware of.
Anyway, the Hagii, aka the Hagï, is once again facing the demotion of the Trecutul. And now, he is watching the decisive match against his rival, FCSpreB. The more exact problem he's facing is this:
A football game is being played on a football pitch of infinite dimensions. For simplicity, you can think of this space as an xOy Cartesian plane.
It has $$$N$$$ ($$$1 \le N \le 100\,000$$$) pairs of players points, which can be described by triplets of the form $$$(x_1,x_2,y)$$$. This means that on the football field where the match is currently taking place, there is a player at position $$$(x_1,y)$$$ who wants to pass to the player at position $$$(x_2,y)$$$.
Except that this is where Gigi the Bo$$ comes in. He has $$$K$$$ ($$$1 \le K \le 100\,000$$$) players, with very wide legs. Specifically, each player can be described by a triplet of numbers $$$(x,y_1,y_2)$$$, meaning that at time $$$T=0$$$, this player blocks all points on the segment bordered by the points $$$(x,y_1)$$$ and $$$(x,y_2)$$$. Thus, at time $$$t$$$, he will block all points between $$$(x,y_1-t)$$$ and $$$(x,y_2-t)$$$ (One can visualize the players strolling downwards with speed = 1 (oY unit) / (time unit)).
We say that a pass $$$(a,b,y)$$$ is successful if for any natural $$$a \le x \le b$$$, we have that at time $$$x-a$$$ the position $$$(x,y)$$$ is not blocked by any segment. One can visualise this process as if a player at position $$$(a,y)$$$ shoots a ball towards $$$(b,y)$$$ with speed = 1 (oX unit) / (time unit).
 |  |  |  |  |  |
Now, the Hagii, a.k.a. the Hagï, knows all this data, but he is busy cleaning up the football field with the vacuum cleaner. So he gives you the data, and asks you which of his passes will be succesful.
First line of input contains the $$$N$$$ and $$$K$$$ of the input (in this order). On each of the following $$$N$$$ lines there will be a triplet described by $$$(x_{1_i},x_{2_i},y_i)$$$, each of them describing a pair of players of Hagii's. We guarantee that $$$x_{1_i} \le x_{2_i}$$$
On the following $$$K$$$ lines, there will be a triplet described by $$$ (x_i,y_{1_i},y_{2_i}) $$$ , each of them describing a player of Gigi's. We guarantee that $$$y_{1_i} \le y_{2_i}$$$
For each pair of players of Hagii's, print either 1, if the pass is successful, or 0, if the pass is unsuccessful.
| Group | Add. constraints | Points | Req. groups | |||
| $$$N$$$ | $$$K$$$ | Special constraints | ||||
| $$$1$$$ | $$$N \le 1\,000$$$ | $$$N \le 1\,000$$$ | — | $$$10$$$ | — | |
| $$$2$$$ | $$$N \le 100\,000$$$ | $$$K \le 100\,000$$$ | There are no players will eventually block the same point on the Ox line (i.e. for each pairs of players of Gigi's, their corresponding $$$x$$$ values are different) | $$$40$$$ | — | |
| $$$3$$$ | $$$N \le 100\,000$$$ | $$$N \le 100\,000$$$ | — | $$$50$$$ | — | |
It is guaranteed that for all tests, we have:
- $$$1 \le x_i, x_{1_i}, x_{2_i}, y_i, y_{1_i},y_{2_i} \le 200\,000$$$
- $$$x_{1_i} \le x_{2_i}, y_{1_i} \le y_{2_i}$$$
4 3 1 6 4 2 6 4 1 3 7 2 3 6 6 7 8 3 6 6 2 6 7
0 0 1 0
5 5 5 7 7 1 8 9 8 9 17 2 4 10 1 10 9 7 11 16 4 7 14 3 4 13 8 11 11 3 9 13
1 0 1 0 0
For the first example:
The pass defined at the beginning of (1 6 4) is blocked by the player defined at the beginning of (3 6 6) at time 2
The pass defined at the beginning of (2 6 4) is blocked by the player defined at the beginning of (6 7 8) at time 4
The pass defined at the beginning of (1 3 7) is not blocked by any player
The pass defined at the start of (2 3 6) is blocked by the player defined at the start of (2 6 7) at time 0
For the second example:
The pass defined at the beginning of (5 7 7) is not blocked by any player
The pass defined at the beginning of (1 8 9) is blocked by the player defined at the beginning of (3 4 13) at time 2
The pass defined at the beginning of (8 9 17) is not blocked by any player
The pass defined at the start of (2 4 10) is blocked by the player defined at the start of (3 4 13) at time 1
The pass defined at the start of (1 10 9) is blocked by the player defined at the start of (3 4 13) at time 2
We also mention the fact that passes can be intercepted at the beginning of the pass or at the end of the pass (imagine the blocker slides into the player that is to shoot/receive the ball)
It's your brother's birthday! Hooray!
You have decided to give him $$$N$$$ presents, each of which contains some number of coins. Present $$$1$$$ contains $$$a_1$$$ coins, present $$$2$$$ contains $$$a_2$$$ coins and so on...
Since both you and your brother are serious competitive programmers (and are skilled in the art of game theory), you have decided to invent a variant of the infamous nim game, called "Birthday Nim".
Birthday Nim is a two player game which requires $$$N$$$ stacks of coins, the $$$i$$$-th of which being $$$a_i$$$ coins tall. In one move, the current player can remove any amount of coins from multiple stacks, provided that they remove at least one coin overall. The two players take turns alternatively, starting with the birthday boy. Birthday Nim ends when all the stacks are empty.
Unfortunately, Birthday Nim can be quite a boring, long and uneventful game. For this reason in particular you have decided to find how many distinct Birthday Nim games last exactly $$$k$$$ turns. Since this number can be very large, you are also satisified with its remainder modulo $$$10^9 + 7$$$.
The first line of input contains two integers $$$N$$$ and $$$K$$$ - the number of presents, and the number of turns, respectively. The second line contains $$$N$$$ space separated integers, the amount of coins in each present ($$$0 \le a_i \le 10^5$$$).
Print one integer, the number of distinct Birthday Nim games that last exactly $$$k$$$ turns. Since this number can be very large, print its remainder modulo $$$10^9 + 7$$$.
- For all tests , $$$0 \le a_i \le 10^5$$$
- Subtask 1 (10 points): $$$N=1$$$, $$$1 \le K \le 10^5$$$;
- Subtask 2 (10 points): $$$N=2$$$, $$$1 \le K \le 500$$$, $$$a_i \le 500$$$;
- Subtask 3 (10 points): $$$N=2$$$, $$$1 \le K \le 5000$$$;
- Subtask 4 (20 points): $$$N=2$$$, $$$1 \le K \le 10^5$$$;
- Subtask 5 (15 points): $$$2 \lt N \le 500$$$, $$$1 \le K \le 500$$$;
- Subtask 6 (35 points): $$$500 \lt N \le 5000$$$, $$$1 \le K \le 5000$$$
2 2 2 3
10
2 50 69 420
362313492
The only possible games are the following :
- [2,3] => [2,0] => [0,0]
- [2,3] => [2,1] => [0,0]
- [2,3] => [2,2] => [0,0]
- [2,3] => [1,0] => [0,0]
- [2,3] => [1,1] => [0,0]
- [2,3] => [1,2] => [0,0]
- [2,3] => [1,3] => [0,0]
- [2,3] => [0,1] => [0,0]
- [2,3] => [0,2] => [0,0]
- [2,3] => [0,3] => [0,0]
Thus, there are 10 possible games that last 2 moves, so print 10 mod $$$10^9+7$$$ = 10.